（可能是我个人觉得单变量比栈会简单很多， 证明了断点单调上升 ，根本不用栈啊

为啥题解区做法都是一样全用栈啊……（怀疑

如果有误，给我讲一下 勿喷（

https://www.luogu.com.cn/record/135024556

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define ce continue
#define pf printf
#define sf scanf
#define int ll
//const int inf=0x3f3f3f3f;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;

const int N=7110;
int gcd(int x,int y){return y?gcd(x,x%y):y;}
inline int rd(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int T;
int n;
int a[N];
int dp[N][N];
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	T=rd();
	while(T--){
		n=rd();
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				dp[i][j]=inf;
		for(int i=1;i<=n;i++)a[i]=rd();
		for(int len=1;len<=n;len++){
			int lk=1;
			for(int l=1;l+len-1<=n;l++){
				int r=l+len-1;
				if(l==r)dp[l][r]=0;
				if(r-l==1)dp[l][r]=a[l];
				for(int k=lk;k<r;k++){
					if(dp[l][r]>max(dp[l][k],dp[k+1][r])+a[k]){
						dp[l][r]=max(dp[l][k],dp[k+1][r])+a[k];
						lk=k;
					}
					if(dp[l][k]>dp[k+1][r])break;
				}
			}
		}
		cout<<dp[1][n]<<endl;
	}
	return 0;
}