Линейный DP с тремя состояниями — задача «Vacations» РАЗБОР

Линейный DP — самый частый шаблон в полосе CF 1100–1500. Его узнают мгновенно: «есть последовательность из $n$ шагов, на каждом шаге $k$ вариантов поведения, между шагами есть локальная зависимость». Состояние — пара (номер шага, в каком режиме закончили этот шаг), переход — выбор следующего режима с учётом разрешённых сочетаний. Эта задача — каноничная разминка такого шаблона: дней немного, состояний всего три, переходы умещаются в десяток строк.

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

---

Что дано

Запланированы $n$ дней. Каждый день описывается одной из четырёх категорий:

• $0$ — спортивный зал закрыт, соревнования нет.
• $1$ — спортивный зал закрыт, соревнование есть.
• $2$ — спортивный зал открыт, соревнования нет.
• $3$ — спортивный зал открыт, соревнование есть.

В каждый день мы выбираем ровно одно из трёх:

• отдыхать (доступно всегда);
• писать соревнование (доступно, если в этот день есть соревнование);
• идти в зал на тренировку (доступно, если зал открыт).

Дополнительное ограничение: нельзя два дня подряд писать соревнование и нельзя два дня подряд ходить в зал. Отдыхать подряд можно сколько угодно.

Нужно минимизировать число дней отдыха.

Ограничения

• $1 \le n \le 100$.
• $a_i \in \{0, 1, 2, 3\}$.
• Время: 1 секунда, память: 256 МБ.

Формат ввода

В первой строке — число $n$. Во второй — $n$ чисел $a_1, a_2, \ldots, a_n$, каждое в диапазоне $0$–$3$.

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

Одно число — минимальное число дней отдыха.

Пример 1

Вход:

4
1 3 2 0

Вывод:

2

Комментарий: день $1$ — соревнование, день $2$ — зал (сменили активность), день $3$ — отдых (зал был вчера), день $4$ — отдых (закрыт всё). Итого $2$ дня отдыха.

Пример 2

Вход:

7
1 3 3 2 1 2 3

Вывод:

0

Комментарий: соревнование, зал, соревнование, зал, соревнование, зал, соревнование (или соревнование, зал, соревнование, зал, соревнование, зал, соревнование — есть несколько корректных раскладок без отдыха).

Пример 3

Вход:

2
2 2

Вывод:

1

Комментарий: оба дня — зал открыт, соревнований нет. В первый день — зал. Во второй идти в зал нельзя (повтор), писать соревнование тоже нельзя (его нет). Значит, второй день — отдых. Или наоборот: первый день — отдых, второй — зал. В любом раскладе один день отдыха.

Разберём первый пример руками

День $1$: тип $1$. Доступно — соревнование или отдых. Зал закрыт. Выбираем соревнование (отдых хуже). День $2$: тип $3$. Доступно — соревнование, зал или отдых. Соревнование нельзя (вчера было). Выбираем зал. День $3$: тип $2$. Доступно — зал или отдых. Зал нельзя (вчера был). Соревнования нет. Остаётся отдых. День $4$: тип $0$. Только отдых.

Итого: один день отдыха в третий день и один в четвёртый — всего $2$. Других раскладок с меньшим числом отдыха не существует (формально проверяется тем же DP).

---

Идея решения

Состояние — пара $(i, s)$, где $i$ — номер последнего рассмотренного дня, $s \in \{0, 1, 2\}$ — что мы делали в этот день: $0$ — отдыхали, $1$ — писали соревнование, $2$ — были в зале. Значение DP — минимальное число дней отдыха в первых $i$ днях при условии, что в день $i$ мы закончили в режиме $s$.

Переход на шаг $i + 1$ зависит от типа дня $a_{i + 1}$:

• В состояние $s = 0$ (отдых) можно прийти из любого предыдущего состояния. Добавляем $+1$ к ответу.
• В состояние $s = 1$ (соревнование) можно прийти, если в день $i + 1$ есть соревнование ($a_{i + 1} \in \{1, 3\}$) и в день $i$ мы не были в режиме «соревнование». Отдых не прибавляется.
• В состояние $s = 2$ (зал) — аналогично: $a_{i + 1} \in \{2, 3\}$ и предыдущее $s \ne 2$.

Если в день $i + 1$ режим недоступен — соответствующее значение DP остаётся «бесконечностью» (помечаем большим числом).

Базовый случай: $dp[0][s] = 0$ для всех $s$ — до начала никакого режима не было, и предыдущий $s$ не накладывает ограничений. Чтобы было удобно, тривиально: при $i = 0$ нет ограничения «два дня подряд», поэтому переходы из $dp[0]$ в $dp[1]$ свободны от условия по предыдущему режиму.

Удобнее всего записать это так: $dp[0][0] = dp[0][1] = dp[0][2] = 0$, и для перехода в $dp[1][s]$ при $s \ne 0$ требуем только «режим $s$ доступен в день $1$», условие «вчера было не $s$» автоматически выполняется (вчера было $0$ из псевдо-предыстории).

Ответ — $\min(dp[n][0], dp[n][1], dp[n][2])$.

Почему это работает

DP корректно описывает все допустимые раскладки. Любая последовательность активностей $(s_1, s_2, \ldots, s_n)$, удовлетворяющая ограничениям задачи, путём индукции по $i$ соответствует одному из значений $dp[i][s_i]$. Минимум по всем валидным $(s_1, \ldots, s_n)$ — это $\min_s dp[n][s]$, а минимум числа отдыхов — то, что мы и считаем.

Корректность ограничения «нельзя дважды подряд» обеспечивается в самой формуле перехода: $dp[i + 1][1]$ берётся как минимум по $dp[i][s']$ с $s' \in \{0, 2\}$, то есть случай $s' = 1$ явно исключён. Аналогично для $s = 2$.

---

Решение: псевдокод

dp_prev[0] = dp_prev[1] = dp_prev[2] = 0
для i от 1 до n:
    t ← a[i]
    INF ← очень большое число
    dp_cur[0] ← min(dp_prev[0], dp_prev[1], dp_prev[2]) + 1
    dp_cur[1] ← INF
    dp_cur[2] ← INF
    если t = 1 или t = 3:                              // доступно соревнование
        dp_cur[1] ← min(dp_prev[0], dp_prev[2])
    если t = 2 или t = 3:                              // доступен зал
        dp_cur[2] ← min(dp_prev[0], dp_prev[1])
    dp_prev ← dp_cur

ответ ← min(dp_prev[0], dp_prev[1], dp_prev[2])

Сложность: $O(n)$ время и $O(1)$ память после rolling (хранятся только три значения за прошлый шаг и три за текущий).

---

Код решения

Различий между языками здесь почти нет. В Python — float('inf') или просто $10^9$ как INF. В C++ — INT_MAX / 2 или константа $10^9$ (большее значение всё равно не понадобится: при $n \le 100$ максимум отдыхов — $100$).

Комментарии по реализации.

• Rolling вместо двумерного массива. Можно было бы держать dp[n + 1][3], но при $n \le 100$ это бессмысленно — три переменных на «прошлый день» хватает. Это общий рефлекс линейного DP: если переход смотрит ровно на один шаг назад, хватит rolling.
• INF как «недостижимо». Значение $10^9$ безопасно: ответ никогда не превышает $n \le 100$, поэтому INF никогда не «закрепится» как реальное значение в ответе. Если бы суммирование могло переполнить INF — нужно было бы аккуратнее.
• Тип int. $n \le 100$ — все промежуточные значения умещаются в int. long long не нужен.
• Никаких краевых проверок. Первый день обрабатывается так же, как любой другой — благодаря выбору $dp_0 = 0$ для всех состояний. Это типичный приём «единая база» в линейном DP.

---

Проверим на всех примерах из условия

Пример 1: $n = 4$, дни $[1, 3, 2, 0]$

Ответ: $\min(2, \text{INF}, \text{INF}) = 2$ ✓

Пример 2: $n = 7$, дни $[1, 3, 3, 2, 1, 2, 3]$

Расклад без отдыха: $1$ (соревнование), $3$ (зал), $3$ (соревнование), $2$ (зал), $1$ (соревнование), $2$ (зал), $3$ (соревнование). На каждом шаге активность доступна и отличается от предыдущей.

Ответ: $\min(1, 0, 1) = 0$ ✓

Пример 3: $n = 2$, дни $[2, 2]$

Ответ: $\min(1, \text{INF}, 1) = 1$ ✓

---

Крайние случаи, на которых можно споткнуться

1. Все дни типа $0$

Никаких активностей нет — ответ $n$ (все дни отдых). DP корректно даёт это: contest и gym всегда INF, rest инкрементируется на каждом шаге.

2. Один день, $n = 1$

$dp[1][\cdot]$ зависит только от типа дня. Если $a_1 = 0$ — ответ $1$. Если $a_1 \in \{1, 2\}$ — ответ $0$ (одна доступная активность). Если $a_1 = 3$ — ответ $0$.

3. Длинный «дрожащий» промежуток

Например, $a = [2, 2, 2, 2, 2]$. Можно зал–отдых–зал–отдых–зал — два отдыха. DP даёт правильный ответ: каждый второй день обязательный отдых, нечётный — зал.

4. Все дни типа $3$ (всё доступно)

Между «соревнование» и «зал» можно чередовать без отдыха — ответ $0$. DP это видит за счёт переходов «соревнование $\leftrightarrow$ зал».

5. $n$ малое, INF большое

$n \le 100$, минимум отдыхов $\le 100$. INF $= 10^9$ — гарантированно не «съест» реальный ответ. Если использовать INT_MAX, при INF + 1 в строке cur_rest = min(...) + 1 будет переполнение int. Поэтому INF берём как $10^9$, а не максимум.

---

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

1. Переходы «вчера было то же самое» не блокируются. Если из prev_contest разрешить переход в cur_contest, нарушается ограничение задачи. Симптом — заниженный ответ.
2. Базовый случай неверен. Если $dp[0][1] =$ INF (как «вчера соревнование не было»), нельзя писать соревнование в день $1$ при $a_1 = 1$ — а в задаче это разрешено. Лекарство — поставить $dp[0][\cdot] = 0$ для всех состояний.
3. Переполнение при INF + 1. В C++ INT_MAX + 1 это UB и обычно даёт минус миллиард. Берите INF как $10^9$ — запас на сложение.
4. min(...) от трёх элементов в C++. Стандартный std::min(a, b) принимает два. Для трёх — std::min({a, b, c}) (с фигурными скобками) или последовательно std::min(std::min(a, b), c).
5. Неверный диапазон цикла. Цикл по дням должен быть от $1$ до $n$ включительно (или эквивалентно по элементам массива $a$). Если случайно остановиться на $n - 1$ — потеряем последний день.
6. Пытаться «сэкономить» состояния. Соблазн объединить «контест и зал» в одно состояние «не отдыхал» — не работает: ограничение «два дня одинаковой активности подряд» завязано на конкретный тип активности.

---

Анализ сложности

• Время: $O(n)$ — по одной итерации цикла на каждый день, в каждой итерации фиксированное число операций.
• Память: $O(1)$ дополнительной (помимо хранения входа). Шесть переменных типа int под текущий и предыдущий слой DP.

---

Что ещё полезно потренировать

• Codeforces 580B «Kefa and Company» — линейный DP / sliding window над отсортированным массивом, тренирует «соседние состояния — соседи в линейке».
• Codeforces 909C «Python Indentation» — линейный DP с накоплением суммы, более сложная свёртка состояний, чем здесь.
• Codeforces 1195C «Basketball Exercise» — двухстрочный линейный DP с переходом «верх или низ», шаблон, родственный текущему.
• acmp.ru задача 116 «Эпсилон-полоса» — задача на линейный DP с двумя состояниями, отличный аналог.

---

Итого

• Идея: линейный DP с состоянием «чем закончили день»; три состояния, переходы по типу дня + запрет повторять активность подряд.
• Сложность: $O(n)$ время, $O(1)$ память после rolling.
• Ловушки: не забыть запрет «вчера было то же», аккуратный INF (не INT_MAX), правильный базовый случай $dp[0][\cdot] = 0$ для всех $s$.