Разбор задачи «Склейка камней по k за ход»

1. Идея

Нужно минимально по стоимости объединить все кучки в одну, если за один ход можно склеить ровно k соседних кучек.

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

Будем рассматривать отрезок кучек от l до r и хранить в dp[l][r] минимальную стоимость, чтобы «максимально склеить» этот отрезок по правилам задачи. Если длина отрезка позволяет в конце получить одну кучку, то в стоимость добавится сумма камней на этом отрезке.

Главная трудность — понять, в каких местах можно разбивать отрезок на две части. Оказывается, нет смысла пробовать все разбиения подряд: достаточно идти по m с шагом k - 1.

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

Наблюдение 1. Когда ответ вообще существует

Если сейчас есть x кучек и мы склеиваем ровно k из них в одну, то количество кучек уменьшается на k - 1.

Значит, начиная с n кучек, мы можем прийти к 1 кучке только если:

(n - 1) % (k - 1) == 0

Если это не так, ответ сразу -1.

Наблюдение 2. Сумма на отрезке нужна много раз

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

Чтобы быстро находить сумму на любом отрезке, используем префиксные суммы:

sum(l, r) = pref[r] - pref[l - 1] в 1-индексации.

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

Если на отрезке длина len, то после серии склеек число кучек уменьшается на кратное k - 1.

Чтобы отрезок можно было свести ровно к одной кучке, должно выполняться:

(len - 1) % (k - 1) == 0

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

Наблюдение 4. Почему разбиения идут с шагом k - 1

В формуле перехода мы делим отрезок [l; r] на [l; m] и [m + 1; r].

В эталонном решении перебираются не все m, а только:

m = l, l + (k - 1), l + 2 * (k - 1), ...

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

3. Алгоритм

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

Читаем n, k и массив a.

Шаг 2. Проверяем возможность получить одну кучку

Если (n - 1) % (k - 1) != 0, выводим -1.

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

Создаём массив pref, где:

• pref[0] = 0
• pref[i] — сумма первых i элементов

Шаг 4. Запускаем DP по отрезкам

Пусть dp[l][r] — минимальная стоимость обработки отрезка.

База:

• для отрезка длины 1 стоимость равна 0, потому что одна кучка уже есть.

Переход:

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

После этого:

• если (len - 1) % (k - 1) == 0, значит весь отрезок можно склеить в одну кучку
• тогда добавляем сумму камней на отрезке

То есть:

dp[l][r] += sum(l, r)

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

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

1. Корректность условия существования ответа

За один ход число кучек уменьшается ровно на k - 1.

Значит, из n кучек можно получить 1 кучку тогда и только тогда, когда разность n - 1 делится на k - 1.

Если не делится, никакая последовательность ходов не поможет.

2. Что означает dp[l][r]

dp[l][r] хранит минимальную стоимость оптимальной обработки отрезка [l; r].

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

3. Почему переход через разбиение правильный

Любой процесс склейки внутри отрезка [l; r] можно рассматривать как комбинацию процессов на двух частях, пока не наступит момент последнего объединения.

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

dp[l][m] + dp[m + 1][r]

Мы перебираем все нужные m с шагом k - 1, то есть все допустимые разбиения, которые могут участвовать в оптимальной структуре решения.

4. Почему нужно добавлять сумму отрезка

Когда отрезок [l; r] можно свести к одной кучке, последний ход объединяет k соседних кучек, и стоимость этого хода равна сумме всех камней на отрезке.

Именно поэтому после нахождения минимальной стоимости подготовки отрезка мы добавляем:

sum(l, r)

Но только тогда, когда длина отрезка вообще позволяет получить одну кучку, то есть когда:

(len - 1) % (k - 1) == 0

5. Почему итоговый ответ — dp[1][n] или dp[0][n-1]

Мы посчитали минимальную стоимость для всех отрезков, значит для всего массива ответ хранится в ячейке, соответствующей всему диапазону.

5. Сложность

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

У нас есть:

• O(n^2) отрезков
• для каждого отрезка перебираются разбиения, их число в среднем O(n / (k - 1)), в худшем случае O(n)

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

• O(n^3)

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

Память:

• O(n^2) на таблицу dp

6. Код на C++17

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

using namespace std;

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

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

    if ((n - 1) % (k - 1) != 0) {
        cout << -1 << '\n';
        return 0;
    }

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

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;

            for (int m = l; m < r; m += (k - 1)) {
                long long cand = dp[l][m] + dp[m + 1][r];
                if (cand < dp[l][r]) dp[l][r] = cand;
            }

            if ((len - 1) % (k - 1) == 0) {
                dp[l][r] += pref[r] - pref[l - 1];
            }
        }
    }

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

7. Код на Python 3

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

if (n - 1) % (k - 1) != 0:
    print(-1)
else:
    pref = [0] * (n + 1)
    for i in range(n):
        pref[i + 1] = pref[i] + a[i]

    INF = 10**18
    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
            best = INF

            m = l
            while m < r:
                cand = dp[l][m] + dp[m + 1][r]
                if cand < best:
                    best = cand
                m += k - 1

            if (length - 1) % (k - 1) == 0:
                best += pref[r + 1] - pref[l]

            dp[l][r] = best

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