先上代码

#include<bits/stdc++.h> 
using namespace std; 
#define ll long long 
#define pb push_back
const int MAXN=7020; 
int a[MAXN],n,T;
ll dp[MAXN][MAXN];
int p,q[MAXN],l,r;
int main(){ 
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 
    cin>>T;
    while (T--){
        cin>>n; for (int i=1;i<=n;i++) cin>>a[i];
        for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) dp[i][j]=1e17;
        for (int i=1;i<n;i++) dp[i][i+1]=a[i];
        for (int k=3;k<=n;k++){
            l=1; r=0; p=1;
            for (int i=k;i<=n;i++){
                while (p<=i&&dp[i-k+1][p]<dp[p+1][i]) {
                    while (l<=r&&a[p]+dp[p+1][i]<=a[q[l]]+dp[q[l]+1][i]) l++;
                    q[++r]=p; p++;
                }
                while (l<=r&&q[l]<=i-k) l++;
                if (p<=i)dp[i-k+1][i]=min(dp[i-k+1][i],a[p]+dp[i-k+1][p]);
                if (l<=r) dp[i-k+1][i]=min(dp[i-k+1][i],a[q[l]]+dp[q[l]+1][i]);
            }
        }
        cout<<dp[1][n]<<'\n';
    }
    return 0;
} 

我好像是按照区间大小进行DP，然后前一部分的思路和题解差不多。
后一部分就很抽象了，维护后半部分答案大于前半部分答案的断点，因为i在增大，所以断点的后半部分答案会继续变大。关键是我是从队尾退决策，再从队尾补决策。
然后这个做法AC了，求hack+可能的解释?