円環 \(0,1,\dots,N-1\) 上での処理を、 \(0,1,\dots,N-1,0,1,\dots,N-1\) と \(2\) 周回して \(1\) つの区間での処理に言い換えるという小技を利用します。
以降、石板 \(i\) と石板 \(N+i\) \((1 \le i \le N)\) とを同一視します。

以下の区間 DP を考えます。

• \(dp[l][r] = \{\) 石板 \(l,l+1,\dots,r\) を \(1\) 枚に結合するための最小のコスト \(\}\)

このままこの区間 DP を行うと時間計算量 \(O(N^3)\) となり、 \(N \le 3000\) なる制約下では実行時間制限に間に合いません。

そこで、 Knuth’s Optimization (Knuth-Yao Speedup) と呼ばれるテクニックを利用します。 英語解説 日本語解説

\(O(N^3)\) の区間 DP は以下でした。

• 区間の長さの短い順に求値する。今求値したい区間を \([i,j]\) とする。
  • \(k=i,i+1,\dots,j-1\) について、以下の最小値が \(dp[i][j]\) となる。
    • \(dp[i][k]+dp[k+1][j]+(A_{i}+A_{i+1}+\dots+A_j)\)

これに少し手を加えることで \(O(N^2)\) とすることができます。

ここで、 \({\rm opt}(i,j)\) を先程の \(O(N^3)\) の区間 DP にて \(dp[i][j]\) を求める際に \(dp[i][k]+dp[k+1][j]+(A_{i}+A_{i+1}+\dots+A_j)\) が最小値を取る \(k\) の中で最大のものであるとします。

もし \({\rm opt}(i,j-1) \le {\rm opt}(i,j) \le {\rm opt}(i+1,j)\) が成り立てば、 DP を以下のように加工することで時間計算量が \(O(N^2)\) となります。

• 区間の長さの短い順に求値する。今求値したい区間を \([i,j]\) とする。
  • \(k={\rm opt}(i,j-1),{\rm opt}(i,j-1)+1,\dots,\min(j-1,{\rm opt}(i+1,j))\) について、以下の最小値が \(dp[i][j]\) となる。
    • \(dp[i][k]+dp[k+1][j]+(A_{i}+A_{i+1}+\dots+A_j)\)

時間計算量が \(O(N^2)\) となる理由は、区間の長さを固定した際に \(k\) の移動量の合計が \(O(N)\) となるからです。

そして、本問では実際に \({\rm opt}(i,j-1) \le {\rm opt}(i,j) \le {\rm opt}(i+1,j)\) が成り立ちます。

証明:
以下形の DP を考えます。本問はまさに以下の形の DP です。

• \(\displaystyle dp[i][j]=\min_{i \le k < j} dp(i,k)+dp(k+1,j)+C(i,j)\)
  
  • ただし、 \(C(i,j)\) は \(i,j\) のみから定まる値

上記の条件が成り立つ十分条件として、全ての \(a \le b \le c \le d\) について以下の双方が成り立てばよいことが知られています。

1. \(C(b,c) \le C(a,d)\)
2. \(C(a,c)+C(b,d) \le C(a,d)+C(b,c)\)

本問では、 \(C(i,j)\) は \(A_i+A_{i+1}+\dots+A_j\) です。このことから、上記の不等式が直ちに示されます。

よって、本問を時間計算量 \(O(N^2)\) で解くことができました。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

ll dp[6005][6005]={0};
int opt[6005][6005];
ll sum[6005]={0};

int main(){
  int N;
  cin >> N;
  for(int i=1;i<=N;i++){
    cin >> sum[i];
    sum[N+i]=sum[i];
  }
  for(int i=1;i<=2*N;i++){
    sum[i]+=sum[i-1];
    opt[i][i]=i;
  }
  for(int len=2;len<=N;len++){
    for(int i=1;i<=N;i++){
      int j=i+len-1;
      ll val=8e18;
      for(int k=opt[i][j-1];k<=min(j-1,opt[i+1][j]);k++){
        if(val >= dp[i][k]+dp[k+1][j]){
          val=dp[i][k]+dp[k+1][j];
          opt[i][j]=k;
        }
      }
      val+=(sum[j]-sum[i-1]);
      dp[i][j]=val;
      if(N+j<=2*N){
        dp[N+i][N+j]=val;
        opt[N+i][N+j]=opt[i][j]+N;
      }
    }
  }
  ll res=8e18;
  for(ll i=1;i<=N;i++){
    res=min(res,dp[i][N+i-1]);
  }
  cout << res << "\n";
  return 0;
}