Лопаем шарики — разбор задачи

1. Идея

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

Главная идея — смотреть не на первый лопнутый шарик, а на последний шарик внутри некоторого отрезка.

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

Отсюда появляется динамика по подотрезкам.

2. Наблюдения

Наблюдение 1. Удобно добавить фиктивные границы

По условию, если соседа слева или справа нет, вместо него используется 1.

Чтобы не разбирать отдельно края массива, добавим:

• слева фиктивный шарик со значением 1,
• справа фиктивный шарик со значением 1.

Пусть новый массив называется b:

• b[0] = 1,
• b[1..n] = a[1..n],
• b[n+1] = 1.

Теперь задача выглядит так: нужно лопнуть все настоящие шарики между 0 и n+1.

Наблюдение 2. Состояние DP

Рассмотрим dp[l][r] — максимальное число монет, которое можно получить, если лопнуть все шарики строго между индексами l и r.

При этом шарики l и r пока не лопаются и считаются границами.

То есть интервал (l, r) — это внутренность между двумя ещё живыми шариками l и r.

Наблюдение 3. Кто лопается последним?

Пусть в интервале (l, r) последним лопается шарик k, где l < k < r.

К моменту, когда мы лопаем k:

• все шарики между l и k уже удалены,
• все шарики между k и r уже удалены,
• значит, ближайшие живые соседи шарика k — это именно l и r.

Тогда за последний шарик k мы получим:

b[l] * b[k] * b[r]

А до этого мы независимо получаем:

• dp[l][k] за левую часть,
• dp[k][r] за правую часть.

Значит,

dp[l][r] = max(dp[l][k] + dp[k][r] + b[l] * b[k] * b[r]) по всем k между l и r.

3. Алгоритм

1. Считываем n и массив a.
2. Строим массив b = [1] + a + [1].
3. Создаём таблицу dp размера (n + 2) x (n + 2), заполненную нулями.
4. Перебираем длину интервала length от 2 до n + 1.
   • Именно с 2, потому что если между l и r нет шариков, то r = l + 1, и значение уже равно 0.
5. Для каждого левого конца l находим r = l + length.
6. Перебираем, какой шарик k будет последним в интервале (l, r).
7. Обновляем dp[l][r] максимумом:
   • dp[l][k] + dp[k][r] + b[l] * b[k] * b[r].
8. Ответ — dp[0][n + 1].

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

Докажем корректность такого перехода.

Рассмотрим произвольный интервал (l, r) и оптимальный способ лопнуть все шарики внутри него.

Среди шариков внутри интервала какой-то шарик k будет лопнут последним.

Тогда:

• все шарики из (l, k) были лопнуты раньше,
• все шарики из (k, r) были лопнуты раньше,
• в момент удаления k внутри (l, r) больше никого не осталось.

Значит, ближайшие живые соседи шарика k — ровно l и r, и за него получаем b[l] * b[k] * b[r].

Кроме того, действия внутри (l, k) и (k, r) не мешают друг другу: это независимые подзадачи. Поэтому суммарная прибыль равна:

• прибыль слева,
• плюс прибыль справа,
• плюс монеты за последний шарик k.

То есть любой оптимальный ответ для (l, r) имеет вид:

dp[l][k] + dp[k][r] + b[l] * b[k] * b[r]

для некоторого k.

С другой стороны, если выбрать любой k и оптимально решить левую и правую подзадачи, а потом лопнуть k последним, получится корректный порядок лопания для всего интервала (l, r).

Значит, достаточно перебрать все возможные k и взять максимум. Именно это и делает формула перехода.

Так как мы считаем интервалы по возрастанию длины, все меньшие подзадачи уже известны к моменту вычисления dp[l][r].

Следовательно, алгоритм правильно находит максимум.

5. Сложность

Размер таблицы dp — O(n^2).

Для каждого состояния dp[l][r] мы перебираем все k между l и r, то есть ещё O(n).

Итоговая сложность:

• по времени: O(n^3)
• по памяти: O(n^2)

При n <= 300 это проходит.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> b(n + 2, 1);
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    vector<vector<long long>> dp(n + 2, vector<long long>(n + 2, 0));

    for (int len = 2; len <= n + 1; len++) {
        for (int l = 0; l + len <= n + 1; l++) {
            int r = l + len;
            long long best = 0;
            for (int k = l + 1; k < r; k++) {
                long long cur = dp[l][k] + dp[k][r] + b[l] * b[k] * b[r];
                if (cur > best) {
                    best = cur;
                }
            }
            dp[l][r] = best;
        }
    }

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