9.6. Виды задач на ДП

В предыдущих разделах я описывал, в первую очередь, общие теоретические основы ДП, иллюстрируя их лишь иногда примерами. Здесь я приведу примеры практического применения ДП в задачах, показывая, какие бывают подзадачи. По ходу я также буду показывать разные приёмы, которые, как мне кажется, могут быть полезны в задачах на ДП.

9.6.1. Линейное ДП

Ну, это довольно просто. Вы для каждого \(i\) считаете некоторую величину, используя ранее насчитанные ответы при меньших \(i\). Пример — задача про 01-последовательности, которую мы уже обсуждали.

Отмечу тут только ещё одну особенность, которая на самом деле относится ко всем видам ДП. Бывают два случая: либо, как в задаче про 01-последовательности, вам просто дано \(N\) и просят посчитать \(ans[N]\), который ни от чего, кроме \(N\), не зависит. А бывает, как в задаче про наибольшую возрастающую последовательность, что вам дают массив \(a\), обычно длины \(N\), и ответ существенно зависит от этого массива — короче говоря, вам или дают только размеры, или ещё какие-то данные линейного (квадратичного и т.п.) размера по \(N\) (\(M\) и т.д.). В последнем случае, как мне кажется, может возникнуть вопрос: а как мы будем считать \(ans[i]\) для промежуточных \(i\)? В большинстве случаев ясно, как: \(ans[i]\) будет ответом для первых \(i\) элементов массива \(a\). Т.е. подзадача от полной задачи будет отличаться просто тем, что выкинули несколько последних элементов массива \(a\), и все. Могут, конечно, быть особые случаи, когда это не так, но это уж слишком :).

Задача 9.22:

Задача 7 «Числа» с региональной олимпиады — 2009

Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел, таких что, если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа смогла вывести не произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей.

Чтобы ответить на поставленный вопрос, Вова решил написать программу, которая позволит ему найти число различных последовательностей неотрицательных целых чисел, в каждой из которых любое число не превосходит C. Он понимал, что такое число могло быть достаточно большим, поэтому ограничился поиском только последних k цифр этого числа.

Требуется написать программу, которая покажет Вове, как можно правильно решить поставленную им задачу.

9.6.2. Многомерное ДП

Ничуть не сложнее предыдущего, просто здесь для каждого \(i\) и \(j\) вычисляете \(ans[i,j]\), или аналогично с тремя и более параметрами; как правило, здесь \(i\), \(j\) и т.д. действительно играют роль в том или ином смысле координат: или напрямую, как в задачах про черепашку, или в некотором другом, но тоже простом смысле. Итак, две таких задачи мы уже разобрали, обсудим ещё классическую задачу на многомерное ДП — задачу про наибольшую общую подпоследовательность.

Итак, даны две строки, \(s_1\) и \(s_2\). Требуется из каждой из них вычеркнуть несколько (возможно, ноль) символов так, чтобы получились одинаковые строки, причём получившиеся строки должны иметь максимальную длину. Пример: если есть две последовательности: acbaaba и bcacb, то ответом будет bab или acb или cab и т.п.: любую из этих строк можно получить вычёркиванием нескольких символов из обеих данных строк, но никакая более длинная строка таким свойством не обладает.

Как решать эту задачу? Первая основная идея ДП: придумаем себе подзадачи. Здесь в качестве подзадач естественно рассмотреть следующие: для каждого \(i\) и \(j\) посчитаем \(ans[i,j]\) — длину наибольшей общей подпоследовательности [1] у первых \(i\) символов первой строки и у первых \(j\) символов второй строки. Например, в приведённом выше примере \(ans[4,3]=2\): это длина наибольшей общей подпоследовательности у строк acba и bca (эта общая подпоследовательность — ba или ca).

Как найти ответ на подзадачу? Вторая основная идея ДП: посмотрим, на что может кончаться решение. Имея ввиду, что нам надо свести нашу подзадачу к более мелким, понятно, что есть два варианта. Если \(i\)-ая буква первой строки не равна \(j\)-ой букве второй, то ясно, что хотя бы одну из них (а, может быть, и две) мы должны вычеркнуть, и дальше решать задачу, когда одна из строк стала короче. Тогда \(ans[i,j]=\max(ans[i-1,j],ans[i,j-1],ans[i-1,j-1])\). Если же эти две буквы совпадают, то ясно, что мы либо не вычёркиваем их, и тогда решение будет решением для \((i-1,j-1)\), к которому приписана одна буква, либо хотя бы одну из них вычёркиваем — короче говоря, \(ans[i,j]=\max(ans[i-1,j-1]+1,ans[i-1,j],ans[i,j-1],ans[i-1,j-1])\). На самом деле, если подумать, то можно упростить эти соотношения и окончательно получить

\[\begin{split}ans[i,j]=\left\{\begin{array}{ll} \max(ans[i-1,j],ans[i,j-1])\qquad&{если\ }s_1[i]\neq s_2[j]\\ ans[i-1,j-1]+1\qquad&{если\ }s_1[i]=s_2[j] \end{array}\right.\end{split}\]

Задача 9.23:

Докажите эти соотношения (они не очевидны!)

Далее все ясно. В двойном цикле вычисляем значения, все понятно. Отмечу, что это как раз и есть многомерное ДП: можно легко записать одну строчку по вертикали, вторую по горизонтали и писать \(ans\) матрицей между ними, как показано в таблице ниже.

  b c a c b
a 0 0 1 1 1
c 0 1 1 2 2
b 1 1 1 2 3
a 1 1 2 2 3
a 1 1 2 2 3
b 1 1 2 2 3
a 1 1 2 2 3

Да, ещё важный момент. «База» динамики. Несложно видеть, что в соответствии с нашим рекуррентным соотношением особыми случаями тут являются \(i=1\) или \(j=1\). Если подумать, то полезно ввести нулевые строку и столбец с \(ans[0,j]=ans[i,0]=0\), и все будет работать.

Задача 9.24:

Напишите процедуру \(out\) для вывода решения в этой задаче.

Задача 9.25:

Подумайте над тем, как тут выводить первое в лексикографическом порядке решение. По-моему, это не очень тривиально.

Отмечу ещё один момент, общий вообще для ДП. Нередко, получив задачу, похожую на другую, знакомую вам, задачу на ДП, хочется просто свести одну к другой, т.е. придумать решение первой задачи в виде «по входным данным для первой задачи получим какие-то входные данные для второй, потом решим вторую, потом по решению второй найдём решение для первой».

Например, есть задача про наибольший подпалиндром, которую мы подробно обсудим в следующем разделе. Кратко: дана строка, требуется вычеркнуть из неё минимальное количество букв так, чтобы получился палиндром — строка, читающаяся одинаково как слева направо, так и справа налево. Правильное и простое решение этой задачи мы обсудим чуть позже, а пока скажу, что может захотеться свести её к только что разобранной нами задаче о наибольшей подпоследовательности. Действительно, пусть нам дана строка \(s\). Возьмём \(s_1=s\), а в качестве \(s_2\) возьмём перевёрнутую \(s\), т.е. строку \(s\), записанную задом наперёд — и найдём наибольшую общую подпоследовательность для \(s_1\) и \(s_2\). Кажется, она и будет ответом на начальную задачу, т.е. наибольшим подпалиндромом для \(s\)… Но не очевидно. Очевидно, что каждый подпалиндром будет общей подпоследовательностью, но обратное неверно. Можно доказать, что среди наибольших общих подпоследовательностей всегда найдется палиндром, т.е. что длина палиндрома таким алгоритмом будет определена верно, но есть примеры, когда есть несколько наибольших общих подпоследовательностей, и не все из них являются палиндромами. Таким образом, есть опасность правильно найти длину, но вывести неправильный ответ.

Поэтому сведение одной задачи к другой здесь, как мне кажется, очень непродуктивный путь. Вам потребуется тщательно проверять его корректность, а может даже оказаться, что задача-то и не сведётся. Более правильно, на мой взгляд, попытаться понять, чем так похожи задачи, и перенести идеи динамического решения второй задачи на первую. Если вы знаете, как решать вторую задачу, то вы знаете, какие надо выбрать подзадачи, как вывести рекуррентное соотношение… — попробуйте перенести эти идеи по аналогии на первую задачу. Не бойтесь придумать динамическое решение!

На самом деле это довольно важная идея!

Пример. Задача: найти наибольшую общую подпоследовательность трёх строк. Т.е. найти наидлиннейшую строку, которую можно получить из любой из трёх данных, вычёркивая некоторые символы. Может показаться, что эту задачу можно свести к только что разобранной, например: найдём наибольшую общую подпоследовательность первых двух строк, а потом найдём наибольшую общую подпоследовательность полученной строки и третьей строки. Или: найдём наибольшую общую подпоследовательность первой и второй строки, потом — второй и третьей строки, а потом — двух найденных. Но нет, так не получится.

Задача 9.26:

Придумайте контрпримеры к двум приведённым способам решения этой задачи

Задача 9.27:

Решите задачу о наибольшей общей подпоследовательности трёх строк по аналогии с задачей для двух строк.

Если вы решили эту задачу, то видите, что методы перенеслись очень легко. Если вы знаете ДП-решение задачи, аналогичной той, что дана вам, то не бойтесь решать данную вам аналогично известной вам: это, наверное, будет несложно. А вот свести одну задачу к другой может быть намного сложнее.

Ещё один пример на эту тему, как я уже сказал, задача про наибольший подпалиндром. Мы её сейчас рассмотрим; я не буду специально указывать на аналогию идей с максимальной подпоследовательностью, но при желании вы можете её проследить.

9.6.3. ДП на подотрезках

Итак, тут мы и рассмотрим задачу о наибольшем подпалиндроме. Это (или близкая к ней задача) — задача с межнара’2000, и это та задача, на которой я сам понял суть ДП. Осенью 2000 года я раздобыл решение Михаила Баутина (на самом деле его раздобыл Александр Пономаренко, и дал копию мне). Решение набирало максбалл (конечно, максбалл — он тогда максбалл на каждой задаче набрал), и я пытался понять, как эти пять строчек могут решать эту задачу?! Но потом вдруг в какой-то момент я понял.

Итак, как решается эта задача. Дана строка \(s\), надо найти её наибольший подпалиндром. Попробую показать, как можно дойти до такого решения (хотя как будет видно далее, окончательная идея — просто стандартная идея ДП на подотрезках, и поэтому можно и сразу догадаться, как решать). Давайте попробуем выбрать такие подзадачи: для каждого \(i\) посчитаем \(ans[i]\) — длину наибольшего подпалиндрома первых \(i\) символов строки \(s\). На что может заканчиваться такой палиндром? Ну, очевидно. Он либо содержит символ \(s[i]\), либо нет. Если не содержит, то все просто — ответ будет равен \(ans[i-1]\). А если содержит?.. Хм. Не так все просто, как могло показаться сначала. Если содержит, то последний символ нашего палиндрома будет \(s[i]\), тогда первый символ палиндрома должен с ним совпадать. Тогда вроде надо бы найти, где первый раз такой символ входит в нашу строку — пусть это позиция \(j\), т.е. \(s[j]=s[i]\), и раньше позиции \(j\) этот символ не встречался. Тогда это вхождение и будет первым символом искомого палиндрома, а оставшаяся часть безусловно будет максимальным подпалиндромом… только для строки \(s[j+1\dots i-1]\), т.е. для подстроки строки начинающейся с позиции \(j+1\) и идущей до позиции \(i-1\). Но мы для такой задачи ответа не знаем, это не есть одна из наших подзадач…

Но тогда ясно, что нужно попробовать немного по-другому. Что-то типа рекуррентного соотношения вырисовывается, но для немного других подзадач. Ну давайте и последуем этой идее. Нам надо знать ответ для любой подстроки, а не только для подстрок, начинающихся с первой позиции строки \(s\)? Так давайте так и поступим!

Итак, новые подзадачи: для каждого \(l\) и \(r\) такого, что \(l\leq r\), вычислим \(ans[l,r]\) — длину наибольшего подпалиндрома для строки \(s[l\dots r]\), т.е. подстроки нашей строки, начинающейся с позиции \(l\) и заканчивающейся позицией \(r\). Ясно, что мы считаем? Если \(s={'\texttt{abcbdefba}'}\), то \(ans[4,8]\) будет хранить длину наибольшего подпалиндрома для строки bdefb (которая равна 3, очевидно). Как вычислить \(ans[l,r]\)? Легко: посмотрим, на что может заканчиваться искомый палиндром. Мы ведь уже имеем общее представление о том, что надо делать. Палиндром либо содержит последний символ строки, т.е. символ \(s[r]\), либо нет. Если нет, то \(ans[l,r]=ans[l,r-1]\). А если содержит? Ну вроде даже понятно: надо найти, где первый раз в нашей текущей строке \(s[l\dots r]\) входит символ, равный \(s[r]\) — пусть это будет позиция \(j\), и тогда \(ans[l,r]=ans[j+1,r-1]+2\) (два, т.к. к палиндрому-ответу на задачу \((j+1,r-1)\) мы дописали два одинаковых символа: \(s[j]\) слева и \(s[r]\) справа).

Казалось бы, всё, но тут ещё возникает стандартная оптимизация, которая часто появляется и в других задачах на ДП. А именно, зачем нам явно искать такой символ \(j\)? Могут быть два варианта: либо \(j=l\), либо \(j\neq l\). В последнем случае, очевидно, это обозначает, что символ \(s[l]\) в ответ не входит, и ответ будет равен \(ans[l+1,r]\) (напомню, что мы рассматриваем пока случай, когда в ответ входит символ \(s[r]\)), во втором случае (\(j=l\)) получаем, что \(s[l]=s[r]\) и очевидно, что ответ равен \(s[l+1,r-1]+2\).

Постарайтесь осознать этот переход, почему и как так получилось, что от цикла поиска \(j\) мы избавились. Такой переход очень часто встречается в задачах на динамику, и надо уметь его видеть. Дополнительное замечание, которое может это объяснить: если \(j\neq l\), то при вычислении \(ans[l+1,r]\) мы бы нашли то же самое значение \(j\), так что зачем его ещё раз искать — ясно, что \(ans[l,r]\) в таком случае так или иначе сведётся к \(ans[l+1,r]\).

Итак, вроде рекуррентное соотношение вырисовалось. Давайте ещё раз для ясности:

  • если \(s[l]=s[r]\), то \(ans[l,r]=2+ans[l+1,r-1]\),
  • иначе есть два варианта: либо в ответ не входит символ \(s[r]\), либо он входит, но тогда не входит \(s[l]\). Т.е. в этом случае ответ есть \(\max(ans[l+1,r],ans[l,r+1])\).

Окончательно:

\[\begin{split}ans[l,r]=\left\{\begin{array}{ll} \max(ans[l+1,r],ans[l,r-1]),\qquad&{если\ }s[l]\neq s[r]\\ ans[l+1,r-1]+2,\qquad&{если\ }s[l]=s[r] \end{array}\right.\end{split}\]

Задача 9.28:

На самом деле строго мы это ещё не доказали. Докажите.

Обратите внимание на «базу» динамики. Я бы рассмотрел с качестве базы \(ans[l,l]=1\) и \(ans[l+1,l]=0\) (второе соотношение — некоторый аналог «нулевой строки»; на него будут ссылаться значения \(ans[l,l+1]\), если \(s[l]=s[l+1]\)).

(Теперь, если вдуматься, то становится видна аналогия с предыдущим пунктом, с задачей о наибольшей общей подпоследовательности двух последовательностей. Она, конечно, не очевидна, но, по-моему, она все-таки есть.)

Итак, общая концепция динамики на подотрезках. Есть некоторая последовательность, строка и т.п. Параметрами динамики будут являться \(l\) и \(r\) — левая и правая граница некоторого куска этой строки / последовательности / …; соответственно, эту подзадачу сводим к более мелким. Инициализация обычно происходит для случаев \(l=r\) или \(l=r-1\). Обращу внимание на то, в каком порядке надо вычислять элементы (конечно, это относится к случаю, когда вы пишете динамику просмотром вперёд или назад, а не рекурсией с запоминанием результата). Иногда бывает так, что для вычисления можно просто организовать пару вложенных циклов по \(l\) и \(r\) типа

for l:=1 to n do
    for r:=l+1 to n do {обратите внимание, что здесь r>l всегда}
        вычислить элемент ans[l,r]

Но в большинстве случаев так не получается, в том числе так не получится в нашей задаче про подпалиндром. Действительно, у нас подзадача \((l,r)\) зависит от \((l,r-1)\), \((l+1,r)\) и \((l+1,r-1)\), т.е. ответы на эти три подзадачи должны быть вычислены до вычисления \((l,r)\). В приведённом же выше коде подзадачи \((l+1,r)\) и \((l+1,r-1)\) вычисляются позже \((l,r)\).

Но очевидно, как эту проблему обойти. Действительно, каждая задача у нас зависит только от задач с более коротким куском (задача \((l,r)\) зависит от задач \((l',r')\) таких, что \(r'-l'<r-l\)), и это почти всегда так в динамике на подотрезках. Поэтому организуем вычисления в порядке увеличения длины куска. У нас будут два вложенных цикла: внешний по длине куска \(len\), внутренний — например, по позиции начала куска \(l\). Соответствующее \(r\) будет равно \(l+len-1\), т.е. получаем такой код:

for len:=1 to n do
    for l:=1 to n-len+1 do begin {обратите внимание на аккуратное значение верхнего предела}
      r:=l+len-1;
      вычислить элемент ans[l,r]
    end;

Таким образом, всегда, когда мы доберёмся до задачи \((l,r)\), все задачи, от которых она зависит, уже будут решены.

Задача 9.29:

Напишите решение задачи про максимальный подпалиндром.

Задача 9.30:

Важное задание! Напишите процедуру \(out\) вывода решения в этой задаче.

Задача 9.31:

Научитесь выводить первое в лексикографическом порядке решение здесь.

Итак, я думаю, понятно, что такое динамика на подотрезках. Это — довольно стандартная и часто встречающаяся идея, и поэтому, имея определённый опыт, мы могли бы сразу при решении задачи о максимальном подпалиндроме догадаться использовать её и не мучиться так, как нам пришлось. Ничего, в будущем догадаемся.

Ещё раз отмечу, что, помимо собственно идеи о динамике на подотрезках, мы ещё тут узнали две полезные идеи. Первая — это то, что иногда бывает нужно расширить список рассматриваемых подзадач, чтобы суметь построить рекуррентное соотношение, и в частности (я надеюсь), поняли, что нет нужды заранее непонятно откуда угадывать набор подзадач, которые надо рассматривать: если мы ошиблись с выбором подзадач, нередко мы увидим свою ошибку и сумеем расширить рассматриваемый набор подзадач, поняв, что именно нам надо.

Вторая идея — это то, что иногда циклы при вычислении ответа на очередную подзадачу можно заменить просто ссылкой на предыдущую подзадачу. Если у вас получается цикл в рекуррентном соотношении, полезно подумать, а нельзя ли от него избавиться. Например, может быть, если выкинуть одну итерацию цикла, то получится в точности цикл, нужный для другой подзадачи? А тогда весь остаток цикла можно убрать, и просто воспользоваться значением для этой подзадачи. Ещё пример на эту идею — задание про монеты, где каждую монету можно использовать сколько угодно раз.

9.6.4. ДП по полной сумме

Это — скорее отдельное замечание, чем отдельный важный тип, но тем не менее заметьте, что иногда бывает так, что одним из параметров динамики мы назначаем некоторую «полную сумму». Например, в задаче про монеты одним из параметров динамики была сумма, которую мы пытаемся набрать.

Ещё пример — дано \(N\) отрезков, требуется сгруппировать их в две группы так, чтобы суммарная длина в первой группе равнялась суммарной длине во второй группе. На самом деле это в точности задача про монеты, надо только определить, можно ли набрать сумму, равную половине общей суммы всех отрезков. Но обратите внимание, что аналогично (при соответствующих ограничениях, конечно) решается и задача о группировке в три группы с равной суммарной длиной, и на четыре и т.д. Например, чтобы разбить на пять групп, можно придумать динамику за \(O(NL^4)\): для каждых \(l_1\), \(l_2\), \(l_3\), \(l_4\) и \(i\) определим, можно ли сгруппировать первые \(i\) отрезков в 5 групп так, чтобы суммарная длина первой равнялась \(l_1\), …, четвёртой — \(l_4\) (а пятой — сколько останется). Переход очевиден: чтобы определить, можно ли так сделать, переберём, в какую группу встаёт \(i\)-ый отрезок и посмотрим на соответствующий ответ для \(i-1\). (Может быть, эту задачу можно и проще решать, но я с ходу такого решения не знаю.)

В общем-то просто, только, может быть, не с ходу может в голову придти, обычно все-таки у нас уже есть некоторый линейный объект, по которому мы и строим динамику (строка, или поле, по которому ползает черепашка, или т.п.). Обратите ещё внимание на то, что придётся считать для каждого \(l_1\), …, \(l_k\), и потому в сложность входит ограничение на суммарную длину отрезков, на которое в других условиях мы могли и не обратить внимание.

Такого рода задачи также называются задачами о рюкзаке, или об упаковке рюкзака, потому что в общепринятой легенде задачи упоминается рюкзак.

Задача 9.32:

Есть \(N\) вещей, у каждой из которых известен вес и стоимость. У нас есть рюкзак грузоподъемности \(W\), т.е. мы можем унести произвольный набор вещей при условии, что их суммарный вес не превосходит некоторого числа \(W\). Требуется среди всех таких наборов выбрать набор с максимальной суммарной стоимостью. Решите эту задачу за \(O(NW)\): найдите ответ и выведите само решение.

9.6.5. ДП на ациклических графах

Вам дан ациклический граф и надо в каждой вершине посчитать некоторую величину, причём её значение для конкретной вершины легко выражается через значения для вершин, из которых в эту идут ребра. Тогда ясно, что можно элементарно применить ДП, единственная проблема — решать подзадачи явно надо в оттопсорченном порядке, и потому совершенно естественно применить тут рекурсию с запоминанием результата.

Пример: найти в ациклическом графе самый длинный путь. Будем решать следующие подзадачи: для каждой вершины определим длину самого длинного пути, заканчивающегося в этой вершине. Подзадача элементарно сводится к более мелким: ответ для данной вершины есть максимум из ответов для всех вершин, из которых в нашу идут ребра, плюс один. Особый случай — если в нашу вершину ни одного ребра не входит, то ответ ноль.

Рекурсия с запоминанием результата пишется легко, прямо по шаблону поиска в глубину; для пометки, в каких вершинах были, не заводим отдельный массив, а используем массив \(ans\) (обратите внимание, что наш граф тут отличается от графа подзадач: в соответствии с тем, как я выше определил граф подзадач, в нем ребра идут в другую сторону):

function find(u):integer;
var max,t,v...
begin
if ans[u]<>-1 then begin
   find:=ans[u];
   exit;
end;
max:=-1;
for v:=1 to n do
    if gr[v,u]<>0 then begin{если из v в u идет ребро}
       t:=find(v);
       if t>max then
          max:=t;
    end;
ans[u]:=max+1;
find:=ans[u];
end;

Вот и все, задача решена. Обратите внимание, что, если бы мы и захотели бы писать ДП с просмотром вперёд/назад, то все равно сначала пришлось бы оттопсортить, т.е. все равно написать поиск в глубину, поэтому рекурсия с запоминанием результата — самое простое и естественное, что тут можно сделать.

Ещё обратите внимание, что тут в коде нет уже привычных нам особых случаев — «базы» динамики (по аналогии с базой индукции). У нас всегда были совсем простые задачи, для которых мы ответ считали отдельно вручную и появлялись if’ы, а тут все получилось автоматически, т.к. «база» ДП — это те вершины, в которые не входят ребра, и все просто. Именно для этого случая \(max\) проинициализирована значением \(-1\).

Задача 9.33:

Напишите процедуру out вывода решения в этой задаче.

9.6.6. ДП на деревьях

Ещё один нередко встречающийся вариант ДП — ДП на деревьях. Пусть вам дано подвешенное дерево (т.е. дерево, в котором выделен корень), и в каждой его вершине надо посчитать некую величину, которая рекуррентно выражается через ответы для сыновей этой вершины. С одной стороны, это, безусловно, частный случай предыдущего пункта, т.к. ребра дерева можно ориентировать по направлению от корня — и получится ациклический граф. Если вам дерево задано в общем виде, то ничего лучше вы, наверное, не придумаете.

(Но все равно случай дерева встречается часто, поэтому имеет смысл динамику на дереве считать отдельным вариантом, а не частным случаем динамики на ациклических графах. В каком-то смысле типичный пример такой динамики — это алгоритм поиска мостов и точек сочленения, где мы вычисляем сложноописываемую величину «минимальная глубина, куда идут ребра из поддерева текущей вершины».)

Кроме обычного варианта, когда вы перебираете детей каждой вершины, есть один способ задания дерева, который нередко встречается прямо во входном файле (или в другом источнике, откуда вы берете входные данные). Вершины нумеруются так, что номер родителя всегда меньше номера любого сына, в частности, номер корня равен 1. Далее, во входном файле просто задано \(N-1\) число — номера родителей для всех вершин от второй до последней (\(N\)-ой). Ясно, что это однозначно задаёт дерево, но это также позволяет иногда намного проще писать ДП. В частности, в этом случае все вершины уже оттопсорчены; ещё отмечу, что здесь легко ложится динамика с просмотром вперёд, т.к. идти от вершины к корню легко, а назад — сложно.

Пример. Можно тут, конечно, дать нетривиальный пример — я его дам ниже в задании — а пока рассмотрим простую задачу. Дано дерево, найти в нем наидлиннейший путь от корня до какого-нибудь листа.

Рекуррентное соотношение очевидно: оно то же, что и в прошлом пункте: ответ для данной вершины есть единица плюс максимум из ответов для сыновей; если сыновей нет, то ответ ноль.

Если дерево задано как-нибудь неудобно, то ничего лучше, чем в прошлом разделе, вы, наверное, не придумаете (ну и не страшно! решение, написанное как в прошлом разделе, будет работать столь же хорошо). Но пусть дерево задано так, как я только что описал. Тогда тут легко пишется динамика с просмотром вперёд:

fillchar(ans,sizeof(ans),0);
for i:=n downto 2 do
    if ans[i]+1>ans[p[i]] then
      ans[p[i]]:=ans[i]+1;

здесь \(p[i]\) — родитель вершины \(i\).

Видите, как элегантно? Осознайте, почему это ещё и правильно и как тут существенно используется то, что дерево задано именно в нужном виде.

Кстати, это доказательство того, что ДП с просмотром вперёд не всегда заменяется «обращением» динамики, как в задаче про Буратино.

Задача 9.34:

Дано дерево. Найдите в нем наибольшее паросочетание, т.е. набор рёбер такой, что 1) никакие два ребра не имеют общего конца, 2) число рёбер максимально возможно. Напишите как само ДП, так и процедуру \(out\) вывода решения.

9.6.7. Игры

В отличие от остальных подпунктов в этом разделе это, конечно, не совсем особый вид задач на ДП, и не особый приём реализации ДП. Это, скорее, класс задач, которые стандартным образом сводятся к ДП, но я его решил рассказать здесь, т.к. довольно логично его рассказывать после динамики на ациклических графах.

Задачи на игры обычно состоят в следующем. Рассматривается некоторая игра, которую обычно можно представить в виде графа, вершины которого являются позициями, которые могут возникнуть в игре, а ребра — возможные в игре ходы. В условии задаются правила, по которым определяется победитель, начальная позиция в игре, и т.д. Требуется определить, кто выиграет «при правильной игре», т.е. при условии, что игроки не будут ошибаться.

Если граф позиций содержит циклы, то это позволяет игре, вообще говоря, продолжаться до бесконечности, что сильно осложняет задачу — такие задачи тоже можно решать, но более сложным методом, не имеющим прямого отношения к динамике. Но часто встречаются игры, в которых граф позиций ациклический. (Могут быть задачи, где на первый взгляд граф содержит циклы, но игра не может продолжаться до бесконечности. Тогда, скорее всего, можно так переопределить позицию, что граф будет все-таки ациклическим; см. пример в задании ниже.)

Если граф ациклический, то задача обычно решается динамикой по позициям. В общем случае конкретные вычисляемые значения могут быть разными, я приведу два примера.

Первый пример. Пусть игроки ходят по очереди и пусть для каждой позиции, из которой нет ходов, определено, кто в ней выиграл — тот, кто в неё пришёл, или наоборот. (Обычно бывает сказано типа «Проигрывает тот, кто не может сделать ход».) Тогда для всех позиции в игре можно определить, кто в ней выигрывает — тот, кто из неё ходит, или его противник. Этот метод часто обсуждается на математических кружках как «метод выигрышных и проигрышных позиций», но по сути это именно алгоритм, причём являющийся частным случаем ДП.

Итак, позицию назовём выигрышной, если тот, кто из неё ходит, выигрывает при правильной игре, иначе проигрышной. Тип каждой позиции однозначно и достаточно легко зависит от типов тех позиций, в которые из неё можно пойти. Действительно, если из позиции \(u\) есть ход в какую-нибудь проигрышную позицию \(v\), то, очевидно, \(u\) — выигрышная позиция, и для победы при нашем ходе из позиции \(u\) нам надо просто сходит в позицию \(v\). Оттуда будет ходить наш противник, и он проиграет, т.к. \(v\) проигрышная — значит, мы выиграем. А вот если из позиции \(u\) нет ходов в проигрышные позиции, т.е. все ходы из неё — в выигрышные, то нам деваться некуда: куда мы не пойдём, противник выиграет. Значит, \(u\) — проигрышная позиция.

Итак, мы получили, фактически, рекуррентное соотношение: как определить тип позиции \(u\), зная типы позиций, в которые возможен ход из \(u\). Тип позиций, из которых нет ходов, мы знаем по условию, поэтому можем с помощью динамики определить типы всех остальных позиций, т.е. решить задачу.

Отмечу, что динамика тут вовсе не обязана быть динамикой на ациклических графах, это может быть и одномерная динамика, и динамика на подотрезках, и динамика по подмножествам (см. ниже) и любая другая, все зависит игры.

Пример. В куче лежит \(N\) камней. За один ход каждый игрок может взять от 1 до \(M\) камней. Проигрывает тот, кто не может сделать ход. Дано \(N\) и \(M\), определите, кто выигрывает при правильной игре.

В этой задаче есть элементарная закономерность и, может быть, вы даже её знаете. Но мы не будем её искать, а будет писать динамическое решение. В массиве \(ans\) храним тип позиции: \(ans[i]=1\), если позиция \(i\) (т.е. куча с \(i\) камнями) выигрышна, и \(ans[i]=2\), если проигрышна. \(ans[0]=2\) по условию (осознайте это!). Динамика пишется легко:

ans[0]:=2;
for i:=1 to n do begin
    ans[i]:=2;
    for j:=1 to m do
        if (j<=i)and(ans[i-j]=2) then
           ans[i]:=1;
end;

Разберитесь, почему это верно. Обратите внимание, что это не динамика по графу, а обычная линейная динамика.

Ещё пример. То же самое, но каждым ходом можно брать не больше, чем предыдущим ходом взял противник. Здесь позиция уже однозначно не определяется количеством камней в куче, надо ещё и хранить, сколько предыдущим ходом взял противник. Т.е. позиция будет \((i,j)\): \(i\) камней в куче и первым ходом можно взять не более \(j\) камней. Додумайте.

Задача 9.35:

Додумайте эту задачу.

Надеюсь, что метод выигрышных и проигрышных позиций понятен и ясно, как его применять даже для произвольных игр такого рода. Второй часто распространённый вариант состоит в следующем. За каждый ход один игрок платит другому некоторую сумму денег, в конечных позициях также определено, сколько игроки должны друг другу заплатить. Требуется определить, какую максимальную сумму денег может получить первый игрок (и, соответственно, потерять второй) при правильной игре.

Такой вид задач также решается динамикой, только теперь для каждой позиции считаем, сколько максимум выигрывает игрок, ходящий из этой позиции. Определяем это легко: перебираем все возможные ход. Пусть за некоторый ход мы должны заплатить противнику сумму \(a\), и при этом мы уже знаем, что ответ для той позиции, куда ведёт этот ход, равен \(b\) (как \(a\), так и \(b\) может быть и положительным, и отрицательным, конечно). Тогда если мы изберём этот ход, то противник сразу получит сумму \(a\), а потом, играя из той позиции, куда мы попали, он получит ещё \(b\), т.е. общий доход противника будет \(a+b\), значит, наш доход будет \((-a-b)\). Выбрав максимум по всем ходам, мы найдём ответ для текущей позиции. Я не буду приводить примера задачи, но подумайте и попробуйте придумать пример сами :)

Аналогично решаются и другие задачи на игры. Т.е. вы всегда вычисляете что-то для каждой позиции, а что именно — зависит от игры. Вычисляете это, перебирая все возможные ходы и используя ответы для тех позиций, куда это ходы ведут.

Примечание

Кстати, можете обратить внимание, что на самом деле только алгоритм такого рода доказывает корректность введения термина «при правильной игре». Откуда мы знаем, что из каждой позиции есть «правильная игра» и откуда мы знаем, что результат определён? А именно по индукции, идя от конечных позиций и используя соображения, аналогичные вышеописанным, мы докажем, что действительно определён.

Иногда бывает так, что игроки в каком-то смысле несимметричны. Например, игроки ходят не по очереди, а для каждой позиции задано, кто из неё ходит: из некоторых позиций ходит всегда Вова, из некоторых — Юра. Тогда все аналогично, только удобнее ответ определять не для «текущего» игрока, а, например, для Вовы (т.е.: если начать играть из этой позиции, то выиграет ли Вова? или: если начать из этой позиции, то какую максимальную сумму заработает Вова?)

Аналогичная идея — в следующей задаче.

Задача 9.36:

В кучке лежат \(N\) камешков. Двое игроков ходят по очереди. Первый своим ходом может взять из кучи от 3 до 5 камешков, второй — добавить в кучу 1 или 2 камешка. Выигрывает тот, после чьего хода камешков в куче не останется или количество камешков в куче будет делиться на 30, либо после чьего хода противник не сможет сходить. Кто выигрывает при правильной игре? (Эту задачу я только что придумал. Может так оказаться, что тут есть простая закономерность, например, всегда выигрывает второй, я не знаю. Но в любом случае придумайте динамическое решение за \(O(N)\).)

9.6.8. ДП на подмножествах

Ещё одна полезная идея ДП бывает следующая. Пусть нам дано некоторое множество объектов. Давайте одним из параметров динамики будет подмножество этого множества, т.е. в простейшем варианте просто посчитаем то, что нам надо, для каждого подмножества этого множества (в более сложном варианте, конечно, могут быть дополнительные параметры у динамики). Конечно, таких подмножеств будет \(2^n\), где \(n\) — количество таких объектов, и потому при больших \(n\) ничего не получится, но при \(n\) до \(20\) и даже немного больше вполне сойдёт. (Кстати, если у вас в задаче есть ограничение типа \(n\leq 18\), то тут можно сразу заподозрить алгоритмы с асимптотикой типа \(2^n\), в том числе, и динамику по подмножествам)

Пример. Паросочетание в произвольном (неориентированном) графе. Дан граф, требуется найти в нем максимальное паросочетание, т.е. набор рёбер такой, что 1) никакие два ребра не имеют общего конца, 2) число рёбер максимально возможно.

Для деревьев эта задача решается легко, см. выше. Для двудольных графов есть алгоритм решения за \(O(N^3)\), а мы попробуем решить эту задачу для произвольных графов.

В принципе, вроде существует полиномиальный алгоритм решения этой задачи для произвольных графов, но я его не знаю и мы его обсуждать не будем. Попробуем научиться решать эту задачу для не очень больших \(n\).

Идея такая: для каждого подмножества множества вершин найдём наибольшее паросочетание (точнее, конечно, его размер) на этом наборе вершин (т.е. размер самого большого паросочетания из всех, у которых все концы всех рёбер лежат в нашем подмножестве вершин). Как это сделать? Ну если это подмножество пустое, то ответ, очевидно, ноль. Иначе возьмём первую вершину. Она либо входит в искомое паросочетание (т.е. является концом одного из рёбер), либо нет. В последнем случае, очевидно, размер паросочетания будет равен ответу для подмножества, не содержащего эту вершину, а в первом случае можно перебрать, какая вершина будет вторым концом соответствующего ребра; для каждого варианта ответ очевиден — единица плюс ответ для подмножества, не содержащего эти две вершины (я тут довольно мутно пишу, но это потому, что объяснить словами это, видимо, непросто, формулы писать я не хочу, т.к. тут все очевидно, и думаю, что вы и так все поняли или даже сами догадались).

Как это писать? Подмножество будем кодировать двоичных числом, в котором \(i\)-ый бит равен единице, если \(i\)-ая вершина входит в подмножество, и нулю, если нет. При этом вершины приходится нумеровать с нуля, а подмножества будут кодироваться числами от 0 до \(2^N-1\). Обратите внимание, что если множество \(A\) является подмножеством \(B\), то номер \(A\) строго меньше, чем номер \(B\). Вполне естественно, что во всех задачах на динамику по подмножествам ответ на данное множество зависит только от ответов на его подмножества, поэтому цикл

for i:=0 to (1 shl N) -1

для любой (ну ладно, для любой нормальной) ДП по подмножествам перебирает подмножества уже в оттопсорченном порядке.

(Т.е. что я тут хочу сказать. Нам надо обработать множества (вершин или чего ещё) в правильном порядке. Обычно ответ на любое множество \(A\) зависит только от ответов на множества, получающиеся выкидыванием из \(A\) некоторых элементов — т.е. только от ответов на подмножества множества \(A\). Может показаться, что перебрать подмножества в подходящем порядке нетривиально, например, может захотеться сначала решить задачи для множеств из одного элемента, потом из двух и т.д. — но так мучиться обычно вовсе не надо: цикл, приведённый выше, тоже перебирает множества в подходящем порядке.)

Раз уж мы так храним множества, то ясно, что без битовой арифметики тут не обойтись. Я не буду особенно комментировать все битовые операции, надеюсь, что вы подумаете и все поймёте. Все на самом деле просто. Смотрите код и разбирайтесь, что тут что делает. Код выглядит страшно, может, можно и проще написать, но на самом деле и это не сложно. Мне, конечно, не нравится break в конце цикла, но ничего проще я не придумал.

for i:=0 to (1 shl N)-1 do begin
    ans[i]:=0;
    for j:=0 to N-1 do {перебираем вершины: они занумерованы от 0 до N-1}
        if (i and (1 shl j)<>0) then begin {если вершина j лежит в нашем множестве}
           t:=ans[i and (not (1 shl j))];   {попробуем ее выкинуть...}
           ans[i]:=t;      {...и посмотреть ответ для того, что получится}

                       {или переберем, какая вершина может быть парной к j-ой:
                        она тоже должна лежать в нашем множестве и быть связана с j ребром}
           for k:=j+1 to N-1 do if (i and (1 shl k)<>0) and (gr[j,k]<>0) then begin
               t:=ans[i and (not (1 shl j)) and (not (1 shl k))];   {выкинем их обе и посмотрим ответ}
               if t+1>ans[i] then
                  ans[i]:=t+1;
           end;
           break; {нам достаточно обработать только одну вершину из множества}
        end;
end;

i and (1 shl j)<>0 проверяет, лежит ли вершина \(j\) в множестве \(i\); i and (not (1 shl j)) даёт номер множества, получающегося из множества \(i\) выкидыванием вершины \(j\), и т.д.

Ещё раз про то, зачем тут break. Нам ведь надо взять какую-нибудь вершину из нашего множества и далее работать с ней (т.е. попробовать её выкинуть или найти ей пару), но по номеру множества найти какую-нибудь вершину, лежащую в нем, сложно (точнее, легко, например, что-нибудь типа ((i-1) and (not i))+1, но я решил не грузить вас ещё битовой арифметикой, да это ещё и для нуля работать не будет), поэтому и написан такой цикл с break.

Задача 9.37:

Напишите процедуру out вывода решения в этой задаче.

В общем, я надеюсь, идея динамики по подмножествам вам понятна. Помимо самой идеи, тут ещё важна нумерация множеств, тот факт, что цикл от \(0\) до \(2^N-1\) все решает, и тот факт, что многие действия делаются битовой арифметикой, в том числе — важное действие — проверка, лежит ли элемент \(j\) в множестве \(i\).

Ещё отмечу, что тут требуется \(O(2^n)\) памяти. Смотрите, как бы вам не вылезти за ограничение памяти.

Задача 9.38:

Задача «Перестановки» с региона-2009.

Задано множество из \(n\) различных натуральных чисел. Перестановку элементов этого множества назовем \(k\)-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее \(k\). Например, если задано множество элементов \(S = {6, 3, 9, 8}\), то перестановка \({8, 6, 3, 9}\) является 2-перестановкой, а перестановка \({6, 8, 3, 9}\) – нет.

Перестановка \({p_1, p_2, \dots, p_n}\) будет лексикографически меньше перестановки \({q_1, q_2, \dots, q_n}\), если существует такое натуральное число \(i\) (\(1 ≤ i ≤ n\)), для которого \(p_j = q_j\) при \(j < i\) и \(p_i < q_i\).

В качестве примера упорядочим все \(k\)-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества \(S\): \({3, 9, 6, 8}\), \({8, 6, 3, 9}\), \({8, 6, 9, 3}\) и \({9, 3, 6, 8}\). Соответственно, первой 2-перестановкой в лексикографическом порядке является множество \({3, 9, 6, 8}\), а четвертой – множество \({9, 3, 6, 8}\).

Требуется написать программу, позволяющую найти \(m\)-ую \(k\)-перестановку в этом порядке.

(конец условия задачи)

…на самом деле это — отличная задача на теорию ДП. Вам потребуется, во-первых, динамика по подмножествам, во-вторых, умение по объекту находить номер. Обратите внимание, что ДП по подмножествам потребует тут ещё одного параметра, кроме самого подмножества, но зато обойдётся без этих мучений с поиском какого-нибудь элемента множества.

9.6.9. ДП по профилю

Считается, видимо, самой страшной темой, хотя, как во всей динамике, ничего страшного тут, если разобраться и прочувствовать. Идея обычно такая: пусть имеется поле размера \(N\times M\), при этом \(N\) может быть велико, зато \(M\) обычно очень мало. Надо с этим полем что-то сделать: покрасить, расставить на нем королей и т.п. ДП по профилю состоит в следующем: назовём профилем решение или т.п. (раскраску, расстановку королей и т.п.) для поля \(1\times M\) [в более сложных задачах может потребоваться поле \(2\times M\) и т.п., и профиль будет не обязательно решение, а что-то ещё… В общем, в общем случае надо думать головой :), но основная идея от этого не изменится]

И теперь основная идея: за счёт того, что \(M\) невелико, всевозможных профилей будет не слишком много, а потому мы сможем сделать следующее. Для каждого \(i\) и для каждого профиля \(p\) решим нашу задачу для поля \(i\times M\) при условии, что последняя строка решения (раскраски, расстановки, …) будет совпадать с профилем \(p\). (Я считаю, что размер поля — \(i\) по вертикали, \(M\) по горизонтали и в этом смысле и говорю о строке. Можно было считать, что \(i\) по горизонтали, \(M\) по вертикали, и требовать, чтобы последний столбец совпадал с профилем \(p\).) В более сложных задачах, конечно, может быть хитрее.

Но давайте лучше рассмотрим пример. Классическая задача на ДП по профилю — Симпатичные узоры. Рассмотрим клеточное поле \(N\times M\). Раскрасим его клетки в белый и чёрный цвета. Назовём полученную раскраску — узор — симпатичным, если нигде внутри него не встречается однотонного квадрата \(2\times 2\). Т.е. в любом квадрате \(2\times 2\) хотя бы одна клетка белая и хотя бы одна клетка чёрная. Даны \(N\), \(M\), требуется найти количество симпатичных узоров размера \(N\times M\).

Будем считать, что \(M\) невелико (очень невелико, так, что мы можем позволить себе работать за \(O(N\cdot 4^M)\) и можем позволить выделить в памяти двумерный массив \(N\times 2^M\)). Решим эту задачу динамикой по профилю.

Профилем назовём раскраску в белый и чёрный цвета строки \(1\times M\); всего разных профилей, очевидно, будет \(2^M\) (пока о симпатичности не говорим). Теперь, для каждого \(i\) (\(1\leq i \leq N\)) и для каждого профиля \(p\) решим следующую задачу: определить количество симпатичных узоров размера \(i\times M\) при условии, что их последняя строка является профилем \(p\). Точнее. Профили, конечно, будем нумеровать от 0 до \(2^M-1\). Пусть \(ans[i,j]\) есть количество симпатичных узоров размера \(i\times M\) таких, что их последняя строчка есть профиль с номером \(j\). Как вычислять \(ans[i,j]\)? Легко. При \(i=1\), очевидно, \(ans[1,j]=1\) для любого \(j\): последняя и единственная строка строго фиксирована, о симпатичности речи пока нет, т.к. все узоры размера \(1\times M\) симпатичны: там просто нет квадратов \(2\times 2\).

Пусть теперь \(i>1\). Попробуем свести задачу \((i,j)\) к задачам с меньшим \(i\). Легко. Последняя строка нашего узора фиксирована, а какой может быть предпоследняя строка? Ясно, что это тоже будет некоторый профиль с номером \(k\) такой, что в последних двух строках нет однотонных квадратов \(2\times 2\) (т.е. профиль \(k\) может идти перед профилем \(j\) тогда и только тогда, когда если пририсовать профиль \(j\) под профилем \(k\), получив прямоугольник \(2\times M\), то он будет симпатичным). Более того, ясно, что если \(k\) может идти перед \(j\), то узоров, в которых последняя строка \(j\), а предпоследняя строка \(k\), будет ровно \(ans[i-1,k]\). Ура!

\[ans[i,j]=\sum_k ans[i-1,k],\]

сумма берётся по всем профилям \(k\) таким, что профиль \(j\) может идти после профиля \(k\).

Ответом на задачу теперь будет просто сумма по всем профилям \(ans[N,i]\):

\[global\_ans=\sum_{i=0}^{2^M-1} ans[N,i].\]

Как и обещал, решение работает за \(O(N\cdot 2^M\cdot 2^M)\) и требует \(O(N\cdot 2^M)\) памяти.

Эта задача была на первой Всероссийской олимпиаде школьников по командному программированию в 2000 году. Мы её тогда решили с третьей попытки; алгоритм, видимо, придумал Сергей Политов. Вот его реализация (дословно то, что мы тогда сдавали на олимпиаде, с добавлением пометок в комментариях):

const inputFile='input.txt';
      OutputFile='output.txt';
var
  a: array[0..31] of String;
  q, r: array[0..31] of Longint;
  t: array[0..31, 0..31] of Byte;
  n, m, c: Integer;
function Bin(a: Byte): String;
var
  s: String[6];
  i: Byte;
begin
  i:= 1; s[0]:= #0;
  while i<1 shl n do
  begin
    if a and i=0 then s:= #48+s else s:= #49+s;
    Inc(i, i);
  end;
  Bin:= s;
end;
function Can(s1, s2: String): Byte;
var
  i: Byte;
  l: Byte absolute s1;
begin
  Can:= 0;
  for i:= 1 to l-1 do
    if(s1[i]=s1[i+1])and(s1[i]=s2[i])and(s1[i]=s2[i+1])
      then Exit;
  Can:= 1;
end;
procedure init;
var
  i: Byte;
begin
  assign(input,InputFile);reset(input);
  Readln(n, m);
  if m<n then begin i:= m; m:= n; n:= i; end;
  close(input);
end;
procedure solve;
var
  i, j, w: Byte;
  g: Integer;
begin
  c:= 1 shl n;
  for i:= 0 to c-1 do a[i]:= Bin(i); { (1) }
  for i:= 0 to c-1 do                { (2) }
    for j:= i to c-1 do begin
      w:= Can(a[i], a[j]); t[i, j]:= w; t[j, i]:= w;
    end;
  for i:= 0 to c-1 do q[i]:= 1;
  for g:= 0 to m-2 do  { (3) }
  begin
    for i:= 0 to c-1 do
    begin
      r[i]:= 0;
      for j:= 0 to c-1 do Inc(r[i], q[j]*t[i, j]); { (4) }
    end;
    q:= r;   { (5) }
  end;
end;
procedure print;
var
  sm: Longint;
  i: Byte;
begin
  assign(output,OutputFile);rewrite(output);
  sm:= 0; for i:= 0 to c-1 do Inc(sm, q[i]);
  Writeln(sm);
  close(output);
end;
begin
  init;
  solve;
  print;
end.

Написано несколько своеобразно, но вполне хорошо и красиво. Обозначения здесь другие, чем в моем изложении выше, в частности, \(N\) и \(M\) поменяны местами (т.е. профилей теперь \(2^N\) и т.д.).

Функция Bin переводит номер профиля в строку; функция Can определяет, может ли один профиль идти за другим, и возвращает 1, если да, и 0, если нет. Процедура solve содержит собственно алгоритм. Сначала (1) насчитываем строки по профилям, потом (цикл (2)) насчитываем матрицу \(t\): \(t[i,j]\) равно единице, если профиль \(j\) может следовать за профилем \(i\) (заметьте, что, очевидно, \(t[i,j]=t[j,i]\)). Ограничение было, видимо, \(M\leq 5\), и потому все массивы до 31.

А далее… Собственно основной цикл ДП — цикл (3). Вы ещё не удивились, что обещанного массива \(N\times 2^M\) нет? Это то, о чем я говорил в конце раздела Фундаментальные основы ДП: что нередко достаточно сохранять не весь массив ответов, а лишь пару его последних строк. Здесь ответы для текущей строки зависят лишь от ответов для предыдущей строки, поэтому можно хранить лишь ответы для текущей и предыдущей строки (номер текущей строки здесь равен, видимо, \(g+2\): \(g\) идёт от 0 до \(m-2\), а номер строки должен идти от \(2\) до \(m\)). В \(q\) хранится ответ для предыдущей строки: \(q[j]\) равно количеству симпатичных узоров размера \(M\times (g+1)\) с профилем \(j\) в конце; — а в \(r\) насчитывается ответ для текущей строки: \(r[i]\) есть количество симпатичных узоров размера \(M\times (g+2)\) с профилем \(i\) в конце. В основном цикле (3) для обработки очередной строки надо насчитать все \(r[i]\), для этого цикл по \(i\). В нем делаем суммирование в соответствии с нашей рекурсивной формулой — цикл (4). Обратите внимание, как получается, что за счёт того, что \(t[i,j]\) равно 1 или 0, мы либо добавляем \(q[j]\) к \(r[i]\), либо нет. После того, как вычислили \(r[i]\) для всех \(i\), переходим к следующему \(g\), и надо выполнить q:=r (5).

Процедура print вычисляет окончательный ответ и выводит его.

Задача 9.39:

Научитесь выводить симпатичный узор по номеру. Т.е. придумайте, в каком порядке симпатичные узоры можно занумеровать так, чтобы вы смогли по номеру вывести узор, и научитесь это делать.

Надеюсь, что идеей динамики по профилю вы прониклись.

Задача 9.40:

Сколько есть способов расставить королей на доске \(N\times M\) так, чтобы никто из них никого не бил? Не знаю, вдруг тут есть формула, но решите эту задачу динамикой по профилю. Тогда вы сможете решить и такую задачу: на доске \(N\times M\) несколько клеток вырезаны. Сколькими способами на оставшихся клетках можно расставить королей, чтобы никто никого не бил?

9.6.10. Динамика по изломанному профилю

Ну, это совсем высший пилотаж. Если вы что-то не поняли выше, то лучше разберитесь в том, что там не поняли. Если же все понимаете и прониклись, то рассматривайте этот раздел как материал к размышлению.

ДП по изломанному профилю позволяет, например, решить задачу про симпатичные узоры за типа \(O(NM\cdot 2^M)\), т.е. теперь тут не \(4^M\), а \(2^M\). Расписывать его вам тут не буду, кратко идея вот в чем: для каждого \(i\) и \(j\) рассмотрим доску, имеющую следующую форму: это прямоугольник \((i+1)\times M\), из последней (\((i+1)\)-ой) строки которой удалены правые \(M-j\) клеток (т.е. левые \(j\) сохранены). Для каждого \(i\), \(j\) и \(p\) определим количество симпатичных узоров для такой доски при условии, что нижние клетки всех \(M\) столбцов образую профиль \(p\) (т.е. профиль теперь частично в \(i\)-ой строке, а частично — в \((i+1)\)-ой). Задача в общем случае сводится к \((i,j-1,p')\), а при \(j=0\) — к \((i-1,M,p)\).

Если вы уже мастера ДП, то подумайте над тем, что я тут написал и, наверное, вы сразу поймёте, в чем суть и даже, может быть, сможете написать.

[1]Почему подпоследовательность? Потому что подстрока — это когда все оставленные символы обязательно идут подряд, а в подпоследовательности не обязательно. Например у abcd подпоследовательностями будут, например, ac и bc, но лишь вторая из них — подстрокой.