1. Идея

Задача просит выбрать порядок лопания шаров так, чтобы сумма заработанных значений была максимальной.

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

Поэтому здесь удобно посмотреть на процесс с другой стороны:

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

Это стандартная идея для интервальной динамики.

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

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

Добавим по краям два фиктивных шара со значением 1:

• слева b[0] = 1,
• справа b[n + 1] = 1.

Тогда исходные шары будут лежать в массиве b[1] ... b[n].

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

Пусть мы хотим узнать максимальную прибыль, которую можно получить, если лопнуть все шары внутри этого интервала.

Обозначим это как dp[l][r].

Тогда если последний шар внутри (l, r) — это k, где l < k < r, то:

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

В этот последний момент по обе стороны от k уже не осталось шаров внутри интервала, поэтому его соседями будут именно l и r.

Значит, прибыль за этот последний шар равна b[l] * b[k] * b[r].

Отсюда переход:

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

3. Алгоритм

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

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

Докажем корректность идеи.

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

В любом допустимом порядке существует шар, который будет лопнут последним внутри этого интервала. Обозначим его k.

Что можно сказать о действиях до этого момента?

• Все шары слева от k внутри интервала, то есть в (l, k), уже лопнуты.
• Все шары справа от k внутри интервала, то есть в (k, r), тоже уже лопнуты.
• Значит, в момент лопания k ближайшими не лопнувшими шарами слева и справа будут именно l и r.

Следовательно, прибыль за последний шар k неизбежно равна b[l] * b[k] * b[r].

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

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

То есть: dp[l][k] + dp[k][r] + b[l] * b[k] * b[r].

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

База тоже верна:

• если между l и r нет ни одного шара, прибыль равна 0;
• именно такими значениями таблица и заполняется изначально.

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

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

5. Сложность

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

Мы перебираем:

• длину интервала,
• левую границу,
• последнюю позицию k.

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

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

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

6. Код на C++17

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

using namespace std;

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

    vector<long long> b(n + 2);
    b[0] = 1;
    b[n + 1] = 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;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

b = [1] + a + [1]
dp = [[0] * (n + 2) for _ in range(n + 2)]

for length in range(2, n + 2):
    for l in range(0, n + 2 - length):
        r = l + length
        best = 0
        for k in range(l + 1, r):
            cur = dp[l][k] + dp[k][r] + b[l] * b[k] * b[r]
            if cur > best:
                best = cur
        dp[l][r] = best

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