Разбор задачи «Убрать ряд цветных шаров»

1. Идея и почему «наивный» 2D-ДД не работает

Нужно минимизировать число добавленных шаров, после которых весь ряд можно убрать, удаляя за ход непрерывную одноцветную группу длины не меньше 2.

Соблазнительно завести dp[l][r] = «минимум вставок, чтобы убрать c[l..r]», и считать, что равные края всегда «склеиваются попарно». Но этого мало. Рассмотрим ряд 2 2 1 1 2. Уберём 1 1, два куска сомкнутся: 2 2 2 — это группа из трёх двоек, она убирается без вставок. Ответ 0. Попарная склейка краёв (c[0] с c[4]) этого не видит и насчитывает лишнюю вставку.

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

2. Состояние

dp[l][r][k] — минимальное число вставок, чтобы убрать подотрезок c[l..r], если слева к шару c[l] уже приклеено k шаров того же цвета (они пришли от ранее выполненных слияний и будут удалены вместе с группой c[l]).

Параметр k достаточно капать до 1: для удаления группы важно лишь, набралось ли в ней >= 2 шаров. Значения k ∈ {0, 1}.

Ответ — dp[0][n-1][0].

3. Переходы

Смотрим на группу шаров цвета c[l], начинающуюся в позиции l (с k приклеенными слева).

Переход 1. Закрыть группу c[l] сейчас. В группе сейчас k + 1 шаров цвета c[l].

• если k = 1 (значит шаров >= 2) — группа убирается без вставок, цена 0;
• если k = 0 (одинокий шар) — нужна одна вставка-партнёр, цена 1.

Затем независимо убираем остаток [l+1 .. r] уже без приклеенных шаров: dp[l][r][k] = (k == 1 ? 0 : 1) + dp[l+1][r][0].

Переход 2. Доращивать группу, слив c[l] с равным c[m]. Для каждого m (l < m <= r) с c[m] == c[l]:

• сначала полностью убираем середину [l+1 .. m-1] за dp[l+1][m-1][0];
• тогда c[l] со своими k приклеенными шарами встаёт вплотную к c[m], и теперь у c[m] слева приклеено k + 1 шаров его цвета (капаем до 1);
• продолжаем решать с этим увеличенным префиксом: dp[l][r][k] = min(dp[l][r][k], dp[l+1][m-1][0] + dp[m][r][1]).

База. Пустой отрезок (l > r) даёт 0 (группа всегда «закрывается» переходом 1 до ухода в пустоту).

4. Почему это верно

Для левой группы цвета c[l] в оптимальном плане либо она удаляется как есть (с тем, что к ней уже приклеено) — это переход 1, либо к ней присоединяется ещё один равный шар c[m] после очистки промежутка — это переход 2. Параметр k корректно переносит «сколько одноцветных уже накоплено слева», что и позволяет учитывать группы из 3 и более шаров. Перебор всех m и минимум покрывают все варианты.

Это в точности схема, известная как ДП «Remove Boxes»: интервал плюс счётчик одинаковых элементов на границе.

5. Сложность

Состояний O(n^2) по отрезкам, помноженное на 2 значения k; переход перебирает m за O(n):

• время: O(n^3);
• память: O(n^2) (множитель 2 по k).

При n <= 300 проходит с большим запасом.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static int dp[305][305][2];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> c(n);
    for (int i = 0; i < n; ++i) cin >> c[i];
    if (n == 0) { cout << 0 << '\n'; return 0; }

    auto get = [&](int l, int r, int k) -> int {
        if (l > r) return 0;
        return dp[l][r][k];
    };

    for (int len = 1; len <= n; ++len) {
        for (int l = 0; l + len - 1 < n; ++l) {
            int r = l + len - 1;
            for (int k = 0; k < 2; ++k) {
                int best = (k == 1 ? 0 : 1) + get(l + 1, r, 0);
                for (int m = l + 1; m <= r; ++m) {
                    if (c[m] == c[l]) {
                        int cand = get(l + 1, m - 1, 0) + get(m, r, 1);
                        if (cand < best) best = cand;
                    }
                }
                dp[l][r][k] = best;
            }
        }
    }

    cout << dp[0][n - 1][0] << '\n';
    return 0;
}

7. Код на Python 3

import sys


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    c = [int(x) for x in data[1:1 + n]]
    if n == 0:
        print(0)
        return

    dp = [[[0, 0] for _ in range(n)] for _ in range(n)]

    def get(l, r, k):
        if l > r:
            return 0
        return dp[l][r][k]

    for length in range(1, n + 1):
        for l in range(0, n - length + 1):
            r = l + length - 1
            cl = c[l]
            for k in (0, 1):
                best = (0 if k == 1 else 1) + get(l + 1, r, 0)
                for m in range(l + 1, r + 1):
                    if c[m] == cl:
                        cand = get(l + 1, m - 1, 0) + get(m, r, 1)
                        if cand < best:
                            best = cand
                dp[l][r][k] = best

    print(dp[0][n - 1][0])


main()