點(diǎn)擊打開鏈接

題意：

有兩排數(shù)，AB依次拿，每次只能從第一/二排最左邊和最右邊拿

問你A拿的和是多少，假設(shè)兩個(gè)人都是很聰明的

思路：

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

出現(xiàn)聰明這個(gè)詞的時(shí)候，這種題不是博弈論就是dp吧

dp[x][y][i][j]表示當(dāng)前玩家從a堆的x~y,b堆的i~j能獲得的最大價(jià)值   

區(qū)間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;	}}