Тренировочная сессия 15: динамика по префиксу с дополнительным состоянием СЕССИЯ

Что тренируем сегодня

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

Обе задачи на этот приём, и они показывают два типовых ответа на этот вопрос. В первой динамика подсчётная: надо посчитать количество расстановок с ограничением «не более k одинаковых подряд», и дополнительная величина отвечает на вопрос «чем мы закончили». Во второй динамика оптимизирующая: надо выбрать k непересекающихся отрезков с максимальной суммой, и дополнительная величина отвечает «сколько уже набрали».

Коридор сегодня — ~CF 1700, верхняя половина «Плато». Обе задачи короткие по коду, но требуют аккуратности в границах и в объёме памяти.

---

Теория

Динамика по префиксу с дополнительным состоянием. Ответ для префикса длины i не выражается через ответы для более коротких префиксов сам по себе — нужна ещё одна величина, описывающая, «в каком мы положении» на границе префикса.

Форма 1 — подсчётная: состояние отвечает «чем закончили».

Когда применять:

• нужно посчитать количество расстановок/последовательностей (а не найти одну лучшую);
• есть ограничение вида «не более k одинаковых элементов подряд»;
• количество элементов каждого типа фиксировано и невелико (до сотен), а ответ требуется по модулю.

Два способа задать состояние:

Способ А — с длиной серии. dp[i][j][последний тип][длина текущей серии]. Прямолинейно, но состояние тяжёлое, и легко ошибиться в обнулении серии при смене типа.

Способ Б — по блокам. dp[i][j][последний тип] — количество расстановок, использующих i элементов первого типа и j второго, где последний блок состоит из элементов указанного типа. Переход добавляет сразу целый блок длины от 1 до предела:

$dp[i][j][A] = \sum_{t=1}^{\min(k_A,\ i)} dp[i-t][j][B]$

Смысл: любая расстановка однозначно разбивается на чередующиеся блоки одинаковых элементов, и мы перебираем длину последнего блока. Раз блоки чередуются, предыдущий блок обязан быть другого типа — отсюда B в правой части. Ограничение «не больше k_A подряд» превращается в верхний предел суммы.

Способ Б короче и надёжнее: серия не хранится, а значит и обнулять её негде.

Начальные значения: dp[0][0][A] = dp[0][0][B] = 1 — пустая расстановка, к которой можно приписать блок любого типа. Ответ — сумма двух значений в конечной ячейке.

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

Каркас способа Б (A = 0, B = 1 — типы элементов):

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

Сложность приёма: $O(n_1 \cdot n_2 \cdot (k_1 + k_2))$.

Форма 2 — оптимизирующая: состояние отвечает «сколько уже набрали».

Когда применять:

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

Состояние: dp[j][i] — максимум, который можно набрать, просмотрев первые i элементов и выбрав ровно j отрезков. Переход всегда из двух вариантов:

1. Не заканчивать отрезок в позиции i — тогда ответ такой же, как для i − 1: dp[j][i−1].
2. Взять отрезок, оканчивающийся в позиции i — он занимает позиции с i − m + 1 по i, значит предыдущие отрезки должны уместиться в первые i − m элементов: dp[j−1][i−m] + (сумма отрезка).

Ответ — dp[k][n].

Почему переход полный: любой допустимый набор либо использует позицию i как конец какого-то отрезка, либо не использует — третьего не дано. Непересечение обеспечивается тем, что во втором варианте мы обращаемся к состоянию i − m, то есть к участку строго левее взятого отрезка.

Сумма отрезка — через префиксные суммы: pref[i] − pref[i−m]. Без них каждый переход стоил бы $O(m)$, и решение подорожало бы ровно во столько же раз.

Про память: таблица размера $(k+1) \times (n+1)$ при $k, n$ до 5000 — это 25 миллионов ячеек, что уже слишком много. Спасает то, что строка j зависит только от строки j − 1: достаточно двух массивов длины n + 1, которые меняются местами на каждом шаге по j.

Каркас приёма — сразу со свёрткой по слоям:

Где ошибаются: обращаются к dp[j−1][i−m] без проверки i ≥ m и получают отрицательный индекс (в Python — молча неверный ответ из-за индексации с конца).

Сложность приёма: $O(nk)$ по времени, $O(n)$ по памяти при свёртке по слоям.

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

Типичные кандидаты в дополнительную величину, по убыванию частоты: сколько объектов уже набрано; чем закончился префикс (последний тип, последний цвет, последняя буква); длина текущей серии; остаток от деления накопленной суммы; номер состояния маленького автомата. Первые два покрывают, наверное, три четверти задач уровня «Плато».

Свёртка памяти. Почти всегда переход смотрит только на предыдущий слой по позиции, поэтому хранить всю таблицу не нужно — хватает двух слоёв, а при аккуратном порядке обхода и одного. Это не украшательство: при $n$ до $10^5$ и k до нескольких тысяч полная таблица не помещается в память, а два слоя — помещаются. Правило простое: если переход идёт «назад на один шаг», сворачиваем по позиции; если «назад на m шагов», хранить придётся m + 1 слоёв или всю строку по одной из осей.

Где приём перестаёт работать. Динамика по префиксу требует, чтобы будущее зависело от прошлого только через состояние. Как только выясняется, что решение на шаге i зависит от того, что будет справа (например, «отрезки не должны пересекаться, но выбирать можно в любом порядке, и выгодность зависит от глобального распределения»), одномерного прохода не хватает. Второй симптом — состояние, которое приходится делать двумерным по величине входа: если в него просится «сколько всего набрано» и это число само по себе до $10^9$, значит приём выбран неверно.

С чем путают. Соседний инструмент — жадность. Отличать их стоит по одному вопросу: правда ли, что локально лучший выбор всегда продолжается до глобально лучшего? В задачах на серии это почти никогда не так — выгодно поставить длинный блок сейчас, но тогда следующий не влезет. Практический признак: если для доказательства жадности нужен обменный аргумент и он не выписывается за пару строк, дешевле сразу писать динамику. Обратная ошибка тоже встречается: динамику пишут там, где хватило бы сортировки, — как в сессии 13, где выбор k вершин сводился к «взять k наибольших вкладов».

---

Задача 1 — CF ~1700 — «Caesar's Legions»

Что дано

В строй нужно поставить n1 пехотинцев и n2 всадников — всех, ровно по одному разу. Строй считается правильным, если в нём нет более k1 пехотинцев подряд и более k2 всадников подряд.

Нужно посчитать количество правильных строёв. Бойцы одного рода войск неотличимы друг от друга: строй задаётся только последовательностью родов войск. Ответ вывести по модулю $10^8$.

Формат ввода: одна строка с четырьмя числами n1, n2, k1, k2 ($1 \le n_1, n_2 \le 100$, $1 \le k_1, k_2 \le 10$).

Формат вывода: количество правильных строёв по модулю $10^8$.

Пример 1:

Ввод:
2 1 1 10

Вывод:
1

Пример 2:

Ввод:
2 3 1 2

Вывод:
5

Пример 3:

Ввод:
2 4 1 1

Вывод:
0

Разберём на примере

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

Подходящих — пять, что и требовалось. Перебор здесь возможен, но при n1 = n2 = 100 расстановок больше, чем атомов в обозримом, — нужна динамика.

Ключевое наблюдение: любой строй однозначно разбивается на чередующиеся блоки. Например, ВПВВП — это В | П | ВВ | П. Ограничения задачи — это ровно ограничения на длину каждого блока: блок пехотинцев не длиннее k1, блок всадников не длиннее k2. Значит вместо «добавляем по одному бойцу и следим за серией» можно «добавляем целый блок», и тогда ограничение проверяется прямо в момент добавления.

Идея решения

Алгоритм в одну фразу: посчитать dp[i][j][тип] — число строёв из i пехотинцев и j всадников, последний блок которых состоит из бойцов указанного типа, добавляя на каждом переходе целый блок допустимой длины.

Почему это работает. Разбиение строя на максимальные блоки одинаковых бойцов единственно, поэтому каждый правильный строй учитывается ровно один раз: он однозначно определяется своим последним блоком и тем, что было до него. Перебирая длину последнего блока t от 1 до min(k, доступное количество), мы перебираем все возможные варианты «чем строй заканчивается», а состояние dp[i−t][j][другой тип] описывает все варианты «что было раньше».

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

Начальные значения dp[0][0][П] = dp[0][0][В] = 1 означают: пустой строй считается «оканчивающимся» и тем, и другим типом, чтобы к нему можно было приписать первый блок любого рода войск. Пустой строй ответом не будет: по условию n1 и n2 не меньше единицы.

Ответ — dp[n1][n2][П] + dp[n1][n2][В] по модулю: строй заканчивается либо блоком пехоты, либо блоком конницы, и эти случаи не пересекаются.

Псевдокод

прочитать n1, n2, k1, k2
MOD = 10^8

dp[0][0][П] = 1
dp[0][0][В] = 1

для i от 0 до n1:
    для j от 0 до n2:
        если i == 0 и j == 0: продолжить

        // последний блок — пехота длины t
        сумма = 0
        для t от 1 до min(k1, i):
            сумма = сумма + dp[i-t][j][В]
        dp[i][j][П] = сумма mod MOD

        // последний блок — конница длины t
        сумма = 0
        для t от 1 до min(k2, j):
            сумма = сумма + dp[i][j-t][П]
        dp[i][j][В] = сумма mod MOD

вывести (dp[n1][n2][П] + dp[n1][n2][В]) mod MOD

Код решения

Комментарии по реализации. Порядок обхода важен: dp[i][j][П] обращается к dp[i−t][j][В] (меньший i, тот же j), а dp[i][j][В] — к dp[i][j−t][П] (тот же i, меньший j). Оба обращения смотрят в уже посчитанные ячейки при обходе i внешним циклом и j внутренним, поэтому дополнительной сортировки состояний не требуется. Внутренние суммы можно накапливать без взятия модуля на каждом шаге: слагаемых не больше десяти, каждое меньше $10^8$, — переполнения нет даже в 32-битном типе, но 64-битный аккумулятор снимает вопрос совсем. Общее число операций — $100 \cdot 100 \cdot 20 = 2 \cdot 10^5$.

Проверка на примерах

Пример 1: n1 = 2, n2 = 1, k1 = 1, k2 = 10.

Ответ 1 + 0 = 1. Наш вывод: 1 — совпадает с ожидаемым (единственный строй ПВП).

Пример 2: n1 = 2, n2 = 3, k1 = 1, k2 = 2. Полный перебор выше дал пять подходящих строёв: ПВПВВ, ПВВПВ, ВПВПВ, ВПВВП, ВВПВП. Динамика даёт dp[2][3][П] + dp[2][3][В] = 5.

Наш вывод: 5 — совпадает с ожидаемым.

Пример 3: n1 = 2, n2 = 4, k1 = 1, k2 = 1. Оба ограничения по единице, значит строй обязан быть строго чередующимся, а при таком чередовании количества родов войск отличаются не больше чем на единицу. Здесь разница 2 — подходящих строёв нет, и все переходы обнуляются.

Наш вывод: 0 — совпадает с ожидаемым.

Крайние случаи

• k1 ≥ n1 и k2 ≥ n2. Ограничения не работают; ответ — число сочетаний, и динамика его честно насчитает.
• k1 = k2 = 1. Только строгое чередование: ответ 2 при n1 = n2, 1 при разнице в единицу и 0 при большей разнице.
• n1 = n2 = 1. Два строя: ПВ и ВП.
• Сильный перекос, например n1 = 100, n2 = 1, k1 = 10. Один всадник разрывает пехоту максимум на два блока, каждый не длиннее 10 — при 100 пехотинцах ответ нулевой.
• Ответ, превышающий модуль. При n1 = n2 = 100 и больших k количество строёв астрономическое; проверка того, что остаток берётся везде.
• Модуль $10^8$, а не $10^9 + 7$. Частая невнимательность: вывод по «привычному» модулю не совпадёт с ответом.

Типичные ошибки

1. Разрешить переход из блока того же типа. Два соседних блока одного рода войск сливаются, и ограничение на серию перестаёт действовать — ответ завышается.
2. Взять не тот модуль. В этой задаче он равен $10^8$.
3. Забыть про начальные значения обоих типов. Если dp[0][0] инициализировать только одним типом, потеряется половина строёв — те, что начинаются с другого рода войск.
4. Считать бойцов различимыми. Ответ тогда домножается на факториалы; в условии строй задаётся только последовательностью родов войск.
5. Хранить длину серии и забыть её обнулить при смене типа. Ошибка способа А, ради которой и стоит предпочесть способ Б.
6. Ограничить перебор длины блока значением k, но не количеством оставшихся бойцов. Обращение к dp[i−t] с отрицательным i−t — либо падение, либо тихо неверный ответ.

Сложность

Время: $O(n_1 n_2 (k_1 + k_2))$ — не более $2 \cdot 10^5$ операций. Память: $O(n_1 n_2)$.

---

Задача 2 — CF ~1700 — «George and Job»

Что дано

Дан массив из n чисел. Нужно выбрать ровно k непересекающихся подотрезков, каждый длины ровно m, так, чтобы суммарная сумма элементов в них была максимальной. Выводится сама максимальная сумма.

Формат ввода:

• Строка 1: три числа n, m, k ($1 \le (m \cdot k) \le n \le 5000$).
• Строка 2: n чисел массива ($1 \le a_i \le 10^9$).

Формат вывода: одно число — максимальная суммарная сумма.

Пример 1:

Ввод:
5 2 1
1 2 3 4 5

Вывод:
9

Пример 2:

Ввод:
7 1 3
2 10 7 18 5 33 0

Вывод:
61

Разберём на примере

Пример 1: массив 1 2 3 4 5, нужен один отрезок длины 2. Вариантов четыре:

Максимум 9. Здесь всё просто, потому что отрезок один.

Пример 2: массив 2 10 7 18 5 33 0, нужно три отрезка длины 1 — то есть просто три элемента, и они автоматически не пересекаются. Берём три наибольших: 33 + 18 + 10 = 61.

А вот при m > 1 и k > 1 жадность «берём самый выгодный отрезок, потом следующий» уже неверна. Возьмём массив 1 100 100 1 при m = 2, k = 2. Самый выгодный отрезок — средний (100 + 100 = 200), но взяв его, мы не сможем разместить второй отрезок: слева и справа остаётся по одному элементу. Правильный ответ — два крайних отрезка: (1 + 100) + (100 + 1) = 202. Локально худший выбор оказался глобально лучшим — типичный признак того, что нужна динамика, а не жадность.

Состояние выберем самое естественное: dp[j][i] — максимум, который можно набрать, если разрешено использовать только первые i элементов и нужно выбрать ровно j отрезков. Позиция i либо является концом какого-то отрезка, либо нет — переход из двух вариантов.

Идея решения

Алгоритм в одну фразу: посчитать префиксные суммы и заполнить таблицу dp[j][i] = max(dp[j][i−1], dp[j−1][i−m] + сумма отрезка, оканчивающегося в i), свернув таблицу до двух строк по j.

Почему это работает. Рассмотрим оптимальный набор из j отрезков внутри первых i элементов. Ровно один из двух случаев:

• Позиция i не входит ни в один отрезок. Тогда весь набор помещается в первые i − 1 элементов, и его значение равно dp[j][i−1].
• Позиция i — конец какого-то отрезка. Отрезок занимает позиции i − m + 1 … i, а остальные j − 1 отрезков лежат левее и не пересекаются с ним, то есть помещаются в первые i − m элементов. Значение равно dp[j−1][i−m] плюс сумма взятого отрезка.

Позиция i не может быть серединой отрезка, потому что мы рассматриваем только отрезки, целиком укладывающиеся в первые i элементов, и разбираем случай по тому, где заканчивается последний из них. Оба случая покрывают все варианты, значит максимум из двух и есть dp[j][i].

Сумма отрезка берётся как разность префиксных сумм — за константу. Без префиксных сумм каждый переход стоил бы $O(m)$, и общее время выросло бы до $O(nkm)$.

Про память. Таблица $(k+1) \times (n+1)$ при обоих значениях до 5000 — 25 миллионов ячеек по 8 байт, то есть двести мегабайт. Это перебор. Но строка j использует только строку j − 1, поэтому достаточно двух массивов длины n + 1: считаем очередную строку и меняем массивы местами.

Про типы. Все элементы положительны, до $10^9$; отрезков до 5000, длина каждого до 5000, но их суммарная длина не превышает n = 5000. Значит ответ не больше $5 \cdot 10^{12}$ — 64-битный тип обязателен.

Псевдокод

прочитать n, m, k, массив a

pref[0] = 0
для i от 1 до n: pref[i] = pref[i-1] + a[i]

prev = массив из n+1 нулей       // строка для j = 0
для j от 1 до k:
    cur = массив из n+1 значений «минус бесконечность»
    для i от j*m до n:                       // раньше j отрезков не помещаются
        вариант1 = cur[i-1]                  // позиция i не конец отрезка
        вариант2 = prev[i-m] + (pref[i] - pref[i-m])
        cur[i] = max(вариант1, вариант2)
    prev = cur

вывести prev[n]

Код решения

Комментарии по реализации. Внутренний цикл стартует не с нуля, а с j · m — раньше этой позиции j непересекающихся отрезков длины m физически не помещаются, и обращение к cur[i−1] в этой зоне давало бы «минус бесконечность». Ячейки левее старта так и остаются недостижимыми, что корректно: обращение prev[i−m] всегда указывает на позицию не меньше (j−1)·m, где предыдущая строка уже осмысленна. В C++ «минус бесконечность» взята как LLONG_MIN / 4, чтобы прибавление суммы отрезка не переполнило тип. По времени решение делает $O(nk)$ операций; при $m = 1$ и $k = n = 5000$ это 25 миллионов — в C++ мгновенно, а в Python такой объём уже требует внимательности к константе (минимум обращений к спискам внутри цикла).

Проверка на примерах

Пример 1: n = 5, m = 2, k = 1, массив 1 2 3 4 5, префиксные суммы 0 1 3 6 10 15.

Наш вывод: 9 — совпадает с ожидаемым.

Пример 2: n = 7, m = 1, k = 3, массив 2 10 7 18 5 33 0. При m = 1 отрезок — это один элемент, и переход превращается в «взять элемент или пропустить». Три строки динамики дают максимумы: одна позиция — 33, две — 33 + 18 = 51, три — 33 + 18 + 10 = 61.

Наш вывод: 61 — совпадает с ожидаемым.

Свой тест на неверность жадности: n = 4, m = 2, k = 2, массив 1 100 100 1. Жадный выбор берёт средний отрезок (200) и остаётся без второго. Динамика: dp[2][4] = dp[1][2] + (100 + 1) = 101 + 101 = 202.

Наш ответ: 202 — совпадает с рассчитанным вручную.

Крайние случаи

• m · k = n. Отрезки покрывают весь массив, выбора нет — ответ равен сумме всех элементов.
• k = 1. Задача сводится к максимальному окну фиксированной длины.
• m = 1. Отрезки — отдельные элементы; ответ равен сумме k наибольших.
• m = n, k = 1. Единственный вариант — весь массив.
• Все элементы одинаковые. Ответ равен m · k · значение; проверка того, что переходы не теряют отрезки.
• Максимальные значения. $n = 5000$, все элементы по $10^9$ — ответ до $5 \cdot 10^{12}$, 32-битный тип переполняется.
• Границы индексов. При i = j · m обращение идёт к prev[(j−1)·m] — самая левая осмысленная ячейка предыдущей строки.

Типичные ошибки

1. Жадный выбор отрезков по убыванию суммы. Тест 1 100 100 1 при m = 2, k = 2 ломает такую жадность.
2. Хранить всю таблицу k × n. Двести мегабайт памяти вместо двух массивов по 5001 ячейке.
3. Отрицательный индекс при i < m. В C++ — обращение за границу массива, в Python — индексация с конца и тихо неверный ответ.
4. Пересчитывать сумму отрезка циклом. Добавляет множитель m к времени работы.
5. Считать в 32-битном типе. Ответ до $5 \cdot 10^{12}$.
6. Инициализировать недостижимые ячейки нулём вместо «минус бесконечности». Тогда динамика «разрешит» набрать j отрезков там, где они не помещаются, и завысит ответ.
7. Начинать внутренний цикл с нуля. Не ошибка сама по себе, если недостижимые ячейки корректно помечены, но именно здесь чаще всего и появляется предыдущий пункт.

Сложность

Время: $O(nk)$ — по одному переходу на ячейку двух свёрнутых строк. Память: $O(n)$ — префиксные суммы и два рабочих массива.

---

Самостоятельная тренировка

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

• Codeforces 706C «Hard problem» (~CF 1600) — дан список строк, каждую можно оставить как есть или развернуть за указанную цену; нужно минимальной ценой добиться, чтобы список оказался отсортированным лексикографически. Дополнительная величина здесь самая маленькая из возможных — один бит «развернули ли предыдущую строку».
• Codeforces 225C «Barcode» (~CF 1700) — прямоугольную картинку из чёрных и белых клеток нужно перекрасить так, чтобы она распалась на вертикальные полосы одного цвета шириной от x до y, а перекрашенных клеток было минимально. Ближайший родственник сегодняшней первой задачи: переход тоже делается сразу целой полосой, а не по одному столбцу.
• Codeforces 106C «Buns» (~CF 1700) — есть запас теста и несколько видов начинки; для каждого вида известно, сколько теста и начинки уходит на изделие и сколько оно стоит; нужно максимизировать выручку. Дополнительная величина — сколько теста ещё осталось; это классический рюкзак, и его стоит уметь писать не задумываясь.
• Codeforces 1409E «Two Platforms» (~CF 1800) — на прямой заданы точки; нужно поставить две горизонтальные платформы длины k так, чтобы они поймали как можно больше точек. Подсказка: отсортируйте точки, посчитайте для каждой позиции, сколько точек ловит платформа, начинающаяся здесь, и заведите массив «лучшее значение справа» — дальше это ровно «выбрать два непересекающихся блока».

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

Обе сегодняшние задачи показывают одно и то же: в динамике самое важное решение принимается до кода — какую величину добавить к позиции. Блочный переход убрал длину серии из состояния; разбор случая «позиция i — конец отрезка или нет» сделал переход полным и коротким. Когда состояние выбрано верно, код занимает десять строк; когда неверно — не спасает никакая аккуратность.

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