概要

円環上の隣接マージ問題は、どこか 1 か所で円を切って直線にした問題として考えると解けます。
直線版は区間 DP で解けますが、そのままでは \(O(N^3)\) なので、Knuth 最適化を使って \(O(N^2)\) に高速化します。

考察

まず、円環ではなく 直線上 に石板が並んでいる場合を考えます。

1. 直線版の区間 DP

区間 \([l, r]\) の石板をすべて結合して 1 枚にする最小コストを

\[ dp[l][r] \]

とします。

区間 \([l, r]\) を最後に 2 つの部分に分けて結合したとすると、
ある \(k\) を使って

• 左側 \([l, k]\) を 1 枚にする
• 右側 \([k+1, r]\) を 1 枚にする
• 最後にその 2 枚を結合する

という形になります。

最後の結合コストは、区間 \([l, r]\) 全体の重さの合計です。
したがって遷移は

\[ dp[l][r] = \min_{l \le k < r} \left( dp[l][k] + dp[k+1][r] \right) + \sum_{i=l}^{r} A_i \]

となります。

これは「スライム合体」などでよく出る典型的な区間 DP です。

---

2. 円環をどう扱うか

円環のままだと、始点と終点が決まっていないので扱いにくいです。
そこで重要な気づきがあります。

円環の最適な結合方法でも、どこか 1 か所を切れば、直線上の結合問題として見られる。

なぜなら、最後の結合では円環全体が 2 つの連続区間に分かれていたはずで、その境目で円を切ればよいからです。

つまり、円環の答えは

• 円をどこか 1 か所で切る
• 直線の問題として最小コストを求める
• それを全ての切り方について試した最小値

になります。

---

3. 配列を 2 倍にして「全ての切り方」を表す

円環の全ての切り方を愚直に試すと面倒なので、配列を 2 回つなげます。

\[ B = A + A \]

例えば

\[ A = [a_1, a_2, a_3, a_4] \]

なら

\[ B = [a_1, a_2, a_3, a_4, a_1, a_2, a_3, a_4] \]

です。

このとき、長さ \(N\) の連続区間

\[ B[i], B[i+1], \dots, B[i+N-1] \]

は、「円環をある位置で切った直線」とちょうど対応します。
よって、答えは

\[ \min_{0 \le i < N} dp[i][i+N-1] \]

です。

---

4. 素朴解法では遅い

直線版の区間 DP をそのままやると、

• 区間の個数が \(O(N^2)\)
• 各区間について分割点 \(k\) を全探索して \(O(N)\)

なので、全体で

\[ O(N^3) \]

かかります。

今回は \(N \le 3000\) なので、\(O(N^3)\) は間に合いません。

---

5. Knuth 最適化で \(O(N^2)\) にする

この DP は

\[ dp[l][r] = \min_{l \le k < r} \left( dp[l][k] + dp[k+1][r] \right) + w(l, r) \]

という形をしており、ここで

\[ w(l,r)=\sum_{i=l}^r B_i \]

です。

この「区間和を足す」タイプの DP には Knuth 最適化 が使えます。
最小値を与える分割点を

\[ opt[l][r] \]

とすると、次の単調性が成り立ちます。

\[ opt[l][r-1] \le opt[l][r] \le opt[l+1][r] \]

つまり、区間 \([l,r]\) の最適な分割点は、
前後の区間の最適分割点の間にあるので、毎回全ての \(k\) を試す必要がありません。

探索範囲を

\[ k = opt[l][r-1] \dots opt[l+1][r] \]

に絞れるため、全体で \(O(N^2)\) になります。

これがこの問題の本質です。

アルゴリズム

1. 配列 \(A\) を 2 回つなげて \(B=A+A\) を作る。
2. 区間和を \(O(1)\) で求めるため、累積和 prefix を作る。
3. dp[l][r] を「\(B[l..r]\) を 1 枚にする最小コスト」とする。
4. opt[l][r] をそのときの最適な分割点とする。
5. 長さ 1 の区間はすでに 1 枚なので $\( dp[i][i]=0 \)$
6. 区間長を 2 から \(N\) まで伸ばしながら DP を埋める。
   • 区間和 $\( total = prefix[r+1]-prefix[l] \)$
   • 分割点は Knuth 最適化により $\( k \in [opt[l][r-1],\ opt[l+1][r]] \)$ だけ試せばよい
   • 遷移 $\( dp[l][r] = \min_k \left(dp[l][k]+dp[k+1][r]+total\right) \)$
7. 最後に、長さ \(N\) の区間について $\( \min_{0 \le i < N} dp[i][i+N-1] \)$ を出力する。

計算量

• 時間計算量: \(O(N^2)\)
• 空間計算量: \(O(N^2)\)

実装のポイント

• 累積和を使って区間和を \(O(1)\) で求めています。
• 円環を扱うために、配列を 2 倍 にしています。
• DP は長さ \(N\) までしか使わないので、length は 2 から N までだけ回せば十分です。
• コストは非常に大きくなる可能性があるので、C++ などで書く場合は long long が必要です。
• opt[l][r] の探索範囲は
  • 左端: opt[l][r-1]
  • 右端: opt[l+1][r]

とし、r-1 を超えないように注意します。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N = data[0]
    A = data[1:1 + N]

    B = A * 2
    M = 2 * N

    prefix = [0] * (M + 1)
    for i, x in enumerate(B):
        prefix[i + 1] = prefix[i] + x

    dp = [[0] * M for _ in range(M)]
    opt = [[0] * M for _ in range(M)]
    for i in range(M):
        opt[i][i] = i

    INF = 10**30

    for length in range(2, N + 1):
        for l in range(0, M - length + 1):
            r = l + length - 1
            left = opt[l][r - 1]
            right = opt[l + 1][r]
            if right > r - 1:
                right = r - 1

            total = prefix[r + 1] - prefix[l]
            row_l = dp[l]

            best = INF
            best_k = left
            for k in range(left, right + 1):
                cost = row_l[k] + dp[k + 1][r] + total
                if cost < best:
                    best = cost
                    best_k = k

            row_l[r] = best
            opt[l][r] = best_k

    ans = min(dp[i][i + N - 1] for i in range(N))
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。