Склейка камней по кругу — разбор

1. Идея

Если бы кучки стояли не по кругу, а в линию, это была бы стандартная задача на динамическое программирование по отрезкам:

• dp[l][r] — минимальная стоимость склеить все кучки на отрезке от l до r в одну;
• если последний шаг разделяет отрезок в точке k, то dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum(l..r)).

Но здесь кучки расположены по кругу. Значит, нужно как-то выбрать, где «разрезать» круг, чтобы превратить его в линию. Поскольку заранее неизвестно, где оптимальный разрез, переберём все варианты одновременно.

Для этого продублируем массив:

• было a[1], a[2], ..., a[n],
• станет b[1..2n] = a[1..n] + a[1..n].

Тогда любой способ разрезать круг соответствует некоторому отрезку длины n в массиве b.

Остаётся:

1. посчитать dp для всех отрезков длины до n в массиве b,
2. взять минимум среди dp[l][l+n-1] для всех l от 1 до n.

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

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

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

• l..k
• k+1..r

Значит, оптимальный ответ для l..r можно выразить через более короткие отрезки.

Наблюдение 2. Цена последнего шага

Когда две готовые части l..k и k+1..r склеиваются, стоимость этого шага равна сумме всех камней на отрезке l..r.

Эта сумма не зависит от того, как именно мы склеивали внутри левой и правой части. Поэтому формула перехода получается очень естественной: dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum(l..r)).

Наблюдение 3. Почему достаточно дублирования

У круга нет фиксированного начала. Если разрезать его перед любой кучкой, получится линейная последовательность длины n.

Все такие линейные последовательности как раз и представлены отрезками длины n в удвоенном массиве.

Значит, ответ для круга — это минимум по всем этим отрезкам.

Наблюдение 4. Быстрый подсчёт суммы на отрезке

В формуле перехода часто нужна сумма sum(l..r). Чтобы не считать её каждый раз заново, используем префиксные суммы:

• pref[i] — сумма первых i элементов массива b,
• тогда sum(l..r) = pref[r] - pref[l-1].

Это позволяет получать сумму за O(1).

3. Алгоритм

Шаг 1. Считать входные данные

Считываем n и массив a.

Если n = 1, ответ сразу 0, потому что склеивать ничего не нужно.

Шаг 2. Построить удвоенный массив

Создаём массив b длины 2n, где:

• b[i] = a[i],
• b[i+n] = a[i].

Так мы получаем все возможные развороты круга в линию.

Шаг 3. Посчитать префиксные суммы

Строим массив pref, чтобы быстро узнавать сумму любого отрезка.

Шаг 4. Динамика по отрезкам

Определим:

• dp[l][r] — минимальная стоимость склеить все кучки на отрезке b[l..r] в одну.

База:

• dp[l][l] = 0, одна кучка уже готова.

Переход:

• перебираем длину отрезка len от 2 до n,
• для каждого l находим r = l + len - 1,
• считаем сумму total = sum(l..r),
• перебираем точку разбиения k от l до r-1,
• обновляем: dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + total).

Шаг 5. Взять лучший разворот

Каждый отрезок длины n:

• b[l..l+n-1], где 1 <= l <= n

соответствует одному способу разрезать круг.

Поэтому ответ:

• минимум среди dp[l][l+n-1].

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

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

1. Корректность формулы для линии

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

Если l = r, на отрезке одна кучка, стоимость склейки равна 0. Это совпадает с базой.

Если l < r, то в оптимальном процессе последним действием обязательно склеиваются две соседние уже собранные кучки. Значит, до последнего действия отрезок был разбит на две части:

• l..k
• k+1..r

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

Стоимость всего процесса тогда равна:

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

Именно это и задаёт переход: dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum(l..r)).

Так как перебираются все возможные k, мы действительно находим минимум.

2. Почему решение для круга сводится к минимуму по отрезкам длины n

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

Оптимальный порядок склеек для круга будет соответствовать некоторому такому разрезу. После дублирования массива любой разрез представлен как отрезок длины n в массиве b.

Следовательно:

• для каждого возможного разреза dp[l][l+n-1] даёт минимальную стоимость для соответствующей линейной записи;
• минимум по всем l от 1 до n даёт минимальную стоимость для исходного круга.

Значит, алгоритм находит правильный ответ.

5. Сложность

Пусть m = 2n.

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

Вычисление:

• длина отрезка — O(n),
• левый конец — O(n),
• точка разбиения — 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];
    }

    if (n == 1) {
        cout << 0 << '\n';
        return 0;
    }

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

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

    vector<vector<long long>> dp(m + 2, vector<long long>(m + 2, 0));
    long long INF = numeric_limits<long long>::max() / 4;

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= m; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;
            long long sum = pref[r] - pref[l - 1];
            for (int k = l; k < r; k++) {
                long long cand = dp[l][k] + dp[k + 1][r] + sum;
                if (cand < dp[l][r]) {
                    dp[l][r] = cand;
                }
            }
        }
    }

    long long ans = INF;
    for (int l = 1; l <= n; l++) {
        long long cand = dp[l][l + n - 1];
        if (cand < ans) {
            ans = cand;
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

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

if n == 1:
    print(0)
else:
    b = [0] + a + a
    m = 2 * n

    pref = [0] * (m + 1)
    for i in range(1, m + 1):
        pref[i] = pref[i - 1] + b[i]

    dp = [[0] * (m + 2) for _ in range(m + 2)]
    INF = 10**30

    for length in range(2, n + 1):
        for l in range(1, m - length + 2):
            r = l + length - 1
            total = pref[r] - pref[l - 1]
            best = INF
            for k in range(l, r):
                cand = dp[l][k] + dp[k + 1][r] + total
                if cand < best:
                    best = cand
            dp[l][r] = best

    ans = INF
    for l in range(1, n + 1):
        if dp[l][l + n - 1] < ans:
            ans = dp[l][l + n - 1]

    print(ans)