#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

int T;
long long dp[7105][7105];

int main(){
	scanf("%d",&T);
	while(T--){
		int n,a[7105];
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		
		memset(dp,0x7f,sizeof(dp));
		
		for(int i=1;i<=n;i++){
			dp[i][i]=0;
			dp[i][i+1]=a[i];
		}
		
		for(int j=3;j<=n;j++){
			int mid[7105];
			mid[j-1]=j-1;
			int l=1;
			int r=0;
			int q[7105];
			memset(q,0,sizeof(q));
			for(int i=j-2;i>0;i--){
				
				mid[i]=mid[i+1];
				while(mid[i]>i&&dp[i][mid[i]-1]>dp[mid[i]][j]) mid[i]-=1;
				while(r>=l&&q[l]>=mid[i]) l+=1;
				dp[i][j]=min(dp[i][j],dp[i][mid[i]]+a[mid[i]]);
				if(r>=l){
					dp[i][j]=min(dp[i][j],dp[q[l]+1][j]+a[q[l]]);
				}
				while(dp[i+1][j]+a[i]<dp[q[r]+1][j]+a[q[r]]&&r>=l) r-=1;
				q[++r]=i;
			}
		}
		printf("%lld\n",dp[1][n]);
	}
	return 0;
}

AC情况

如上链接所示，subtask0全部TLE，而这个点理应是数据最小的才对啊... 恳请大佬看一眼问题所在