思路：定义一个四维状态的数组，记录每个状态先手的最优值。
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> #define Maxn 30 using namespace std; int ans[Maxn][Maxn][Maxn][Maxn],suma[Maxn],sumb[Maxn]; void init() { memset(ans,0,sizeof(ans)); memset(suma,0,sizeof(suma)); memset(sumb,0,sizeof(sumb)); } inline int Max(int a,int b,int c,int d) { a=a>b?a:b; c=c>d?c:d; return a>c?a:c; } int dfs(int l,int r,int l1,int r1) { if(l>r&&l1>r1) return 0; if(ans[l][r][l1][r1]) return ans[l][r][l1][r1]; int levsum=suma[r]-suma[l-1]+sumb[r1]-sumb[l1-1]; int ans1=0,ans2=0,ans3=0,ans4=0; if(l<=r){ ans1=levsum-dfs(l+1,r,l1,r1); ans2=levsum-dfs(l,r-1,l1,r1); } if(l1<=r1){ ans3=levsum-dfs(l,r,l1+1,r1); ans4=levsum-dfs(l,r,l1,r1-1); } return ans[l][r][l1][r1]=Max(ans1,ans2,ans3,ans4); } int main() { int n,i,j,t,x; scanf("%d",&t); while(t--){ init(); scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&x); suma[i]=suma[i-1]+x; } for(i=1;i<=n;i++){ scanf("%d",&x); sumb[i]=sumb[i-1]+x; } printf("%d ",dfs(1,n,1,n)); } return 0; }