题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4597
题目大意：
有两行卡片，每个卡片都有各自的权值。
两个人轮流取卡片，每次只能从任一行的左端或右端取卡片。
假设两人都足够聪明，求先手能够取到的最大权值之和。
解题思路：
这题就归为区间DP吧，设dp[l1][r1][l2][r2]表示取完第一行[l1,r1]和第二行[l2,r2]的卡片时，先手能够获得的最大权值。
那么跟(l1,r1,l2,r2)关联的区间只有四个：
(l1+1,r1,l2,r2)
(l1,r1-1,l2,r2)
(l1,r1,l2+1,r2)
(l1,r1,l2,r2-1)
那么状态转移方程就为：
dp[l1][r1][l2][r2]=max(dp[l1][r1][l2][r2],sum-solve(l1+1,r1,l2,r2))，(l1<=r1)
dp[l1][r1][l2][r2]=max(dp[l1][r1][l2][r2],sum-solve(l1,r1-1,l2,r2))，(l1<=r1)
dp[l1][r1][l2][r2]=max(dp[l1][r1][l2][r2],sum-solve(l1,r1,l2+1,r2))，(l2<=r2)
dp[l1][r1][l2][r2]=max(dp[l1][r1][l2][r2],sum-solve(l1,r1,l2,r2-1))，(l2<=r2)
其中sum为第一行[l1,r1]和第二行[l2,r2]卡片权值之和，
从子区间推过来相当于先后手顺序发生了改变，所以sum-子区间最优解相当于取反，就是原来先手的操作变成后手，后手变成先手。
那么我们为什么要从最优子区间解里推过来呢，那样不就变成了让后手有了较优解了吗，不就让先手获得的权值变少了吗？因为题目说了两人足够聪明，选取的都是最优解。
代码：
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<string>
#define lc(a) (a<<1)
#define rc(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name) freopen(name,"r1",stdin)
#define fout(name) freopen(name,"w",stdout)
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define _for(i,start,end) for(int i=start;i<=end;i++)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const int N=;
const int INF=0x3f3f3f3f;
const double eps=1e-; int a[N],b[N];
int dp[N][N][N][N]; int solve(int l1,int r1,int l2,int r2){
if(dp[l1][r1][l2][r2]!=-)
return dp[l1][r1][l2][r2]; int ans=,sum=;
if(l1<=r1)
sum+=a[r1]-a[l1-];
if(l2<=r2)
sum+=b[r2]-b[l2-];
//从子区间推过来相当于先后手顺序发生了改变，所以用减相当于取反
if(l1<=r1){
ans=max(ans,sum-solve(l1+,r1,l2,r2));
ans=max(ans,sum-solve(l1,r1-,l2,r2));
}
if(l2<=r2){
ans=max(ans,sum-solve(l1,r1,l2+,r2));
ans=max(ans,sum-solve(l1,r1,l2,r2-));
} return dp[l1][r1][l2][r2]=ans;
} int main(){
FAST_IO;
int t;
scanf("%d",&t);
while(t--){
memset(dp,-,sizeof(dp));
int n;
scanf("%d",&n);
_for(i,,n){
cin>>a[i];
a[i]+=a[i-];
}
_for(i,,n){
cin>>b[i];
b[i]+=b[i-];
}
printf("%d\n",solve(,n,,n));
}
return ;
}