hdu 4597 Play Game 区间dp

点击打开链接

题意：

有两排数，AB依次拿，每次只能从第一/二排最左边和最右边拿

问你A拿的和是多少，假设两个人都是很聪明的

思路：

http://blog.csdn.net/shuangde800/article/details/10277697

出现聪明这个词的时候，这种题不是博弈论就是dp吧

dp[x][y][i][j]表示当前玩家从a堆的x~y,b堆的i~j能获得的最大价值   

区间dp

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll a[25],b[25],dp[25][25][25][25];ll solve(int l1,int r1,int l2,int r2){	if(dp[l1][r1][l2][r2]!=-1) return dp[l1][r1][l2][r2];	if(l1>r1) dp[l1][r1][l2][r2] = 0;	if(l2>r2) dp[l1][r1][l2][r2] = 0;	ll sum = 0,ans = 0;	if(l1<=r1)		sum += a[r1]-a[l1-1];	if(l2<=r2)		sum += b[r2]-b[l2-1];	if(l1<=r1){		ans = max(ans,sum-solve(l1+1,r1,l2,r2));		ans = max(ans,sum-solve(l1,r1-1,l2,r2));	}	if(l2<=r2){		ans = max(ans,sum-solve(l1,r1,l2+1,r2));		ans = max(ans,sum-solve(l1,r1,l2,r2-1));	}	return dp[l1][r1][l2][r2] = ans;}int main(){	int T; scanf("%d",&T);	while(T--){		memset(dp,-1,sizeof(dp));		memset(a,0,sizeof(a));		memset(b,0,sizeof(b));		int n; scanf("%d",&n);		for(int i=1; i<=n; i++){			scanf("%d",&a[i]);			a[i] += a[i-1];		}		for(int i=1; i<=n; i++){			scanf("%d",&b[i]);			b[i] += b[i-1];		}		cout << solve(1,n,1,n) << endl;	}}