Минимальная стоимость склейки камней — разбор

1. Идея

Нужно объединить все кучки в одну, каждый раз склеивая только две соседние. Стоимость одной склейки равна сумме размеров этих двух кучек.

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

Это наводит на динамическое программирование по подотрезкам.

Будем считать dp[l][r] — минимальную стоимость, чтобы склеить в одну кучку все кучки с индексами от l до r.

Тогда ответ — dp[1][n] в C++-версии с 1-индексацией или dp[0][n-1] в Python-версии с 0-индексацией.

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

Наблюдение 1. Последняя операция на отрезке

Если мы хотим склеить все кучки на отрезке [l, r] в одну, то в самой последней операции этот отрезок был разбит на две части:

• [l, k]
• [k+1, r]

Сначала каждая из них независимо склеивается в одну кучку, а потом эти две итоговые кучки склеиваются между собой.

Значит, если последний разрез был в позиции k, стоимость будет такой:

• минимальная стоимость склейки левой части,
• плюс минимальная стоимость склейки правой части,
• плюс стоимость последней склейки этих двух частей.

Наблюдение 2. Стоимость последней склейки

После того как части [l, k] и [k+1, r] уже склеены внутри себя, остаются две соседние кучки. Их размеры равны суммам камней на этих отрезках.

Итоговая стоимость последнего склеивания равна сумме всех камней на отрезке [l, r].

То есть переход:

dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum(l, r))

для всех k от l до r-1.

Наблюдение 3. Нужны быстрые суммы на отрезках

Сумма sum(l, r) встречается очень часто, поэтому её надо уметь считать за O(1).

Для этого используем префиксные суммы:

• pref[i] — сумма первых i кучек.

Тогда сумма на отрезке:

• в 1-индексации: pref[r] - pref[l - 1]
• в 0-индексации: pref[r + 1] - pref[l]

Наблюдение 4. База

Если отрезок состоит из одной кучки, ничего склеивать не нужно, значит:

dp[l][l] = 0

3. Алгоритм

Заполним таблицу dp по возрастанию длины отрезка.

Шаги

1. Считываем n и массив a.
2. Строим массив префиксных сумм.
3. Создаём таблицу dp, изначально заполненную нулями.
4. Перебираем длину отрезка len от 2 до n.
5. Для каждого отрезка [l, r] такой длины:
   • находим сумму всех камней на отрезке;
   • перебираем позицию разреза k;
   • обновляем минимум по формуле: dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + sum(l, r))
6. Выводим ответ.

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

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

Рассмотрим любой отрезок [l, r].

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

• левая часть [l, k]
• правая часть [k+1, r]

Иначе последняя операция не могла бы покрывать весь отрезок.

Значит, любая допустимая стратегия для [l, r] имеет вид:

1. склеить [l, k] в одну кучку;
2. склеить [k+1, r] в одну кучку;
3. склеить эти две итоговые кучки.

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

dp[l][k] + dp[k+1][r] + sum(l, r)

Остаётся выбрать лучший k. Именно это и делает переход динамики.

Почему можно заполнять dp по длине отрезка? Потому что при вычислении dp[l][r] используются только значения для более коротких отрезков:

• [l, k]
• [k+1, r]

Они уже будут посчитаны раньше.

База dp[l][l] = 0 тоже верна: одна кучка уже склеена сама с собой, дополнительных операций не требуется.

Следовательно, после заполнения всей таблицы значение dp[1][n] или dp[0][n-1] действительно равно минимальной суммарной стоимости.

5. Сложность

Пусть n — количество кучек.

• Длина отрезка: O(n)
• Левая граница: O(n)
• Точка разбиения k: O(n)

Итого:

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

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

6. Код на C++17

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

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

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

    vector<long long> pref(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i];
    }

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

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            long long best = numeric_limits<long long>::max();
            long long sum = pref[r] - pref[l - 1];

            for (int k = l; k < r; k++) {
                long long cur = dp[l][k] + dp[k + 1][r] + sum;
                if (cur < best) {
                    best = cur;
                }
            }

            dp[l][r] = best;
        }
    }

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

7. Код на Python 3

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

pref = [0] * (n + 1)
for i in range(n):
    pref[i + 1] = pref[i] + a[i]

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

for length in range(2, n + 1):
    for l in range(0, n - length + 1):
        r = l + length - 1
        total = pref[r + 1] - pref[l]
        best = 10**30
        for k in range(l, r):
            cur = dp[l][k] + dp[k + 1][r] + total
            if cur < best:
                best = cur
        dp[l][r] = best

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