分析：两个人都足够聪明，因此每个阶段都拿最大的。dp[sa][ea][sb][eb]分别表示区间1的开始为sa，结束为ea，区间2的开始为sb，结束为eb时能拿到的最大值。之后分别从四个方向上拿，是个搜索的过程。
#include<iostream>using namespace std;int dp[25][25][25][25]; //dp[sa][ea][sb][eb],分别表示区间1的开始，结束，区间2的开始，结束int a[25],b[25];int max(int a,int b){return a>b?a:b;}int DFS(int sa,int ea,int sb,int eb,int sum) //两个人都很聪明，都尽量拿大的{int ma;if(sa>ea && sb>eb)//边界return 0;if(dp[sa][ea][sb][eb]>0)//记忆化return dp[sa][ea][sb][eb];ma=0;if(sa<=ea){ma=max(ma,sum-DFS(sa+1,ea,sb,eb,sum-a[sa])); //取出区间1开始的值ma=max(ma,sum-DFS(sa,ea-1,sb,eb,sum-a[ea])); //取出区间1结尾的值}if(sb<=eb){ma=max(ma,sum-DFS(sa,ea,sb+1,eb,sum-b[sb])); //取出区间2开始的值ma=max(ma,sum-DFS(sa,ea,sb,eb-1,sum-b[eb])); //取出区间2结尾的值}dp[sa][ea][sb][eb]=ma;return ma;}int main(){int T,N,i,sum;ios::sync_with_stdio(false);cin>>T;while(T–){cin>>N;sum=0;for(i=1;i<=N;i++)sum+=(cin>>a[i],a[i]);for(i=1;i<=N;i++)sum+=(cin>>b[i],b[i]);memset(dp,0,sizeof(dp));cout<<DFS(1,N,1,N,sum)<<endl;}return 0;}
，与其用泪水悔恨今天，不如用汗水拼搏今天。
