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

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 ll a[25],b[25],dp[25][25][25][25];
 6 
 7 ll solve(int l1,int r1,int l2,int r2){
 8     if(dp[l1][r1][l2][r2]!=-1) return dp[l1][r1][l2][r2];
 9 
10     if(l1>r1) dp[l1][r1][l2][r2] = 0;
11     if(l2>r2) dp[l1][r1][l2][r2] = 0;
12 
13     ll sum = 0,ans = 0;
14     if(l1<=r1)
15         sum += a[r1]-a[l1-1];
16     if(l2<=r2)
17         sum += b[r2]-b[l2-1];
18 
19     if(l1<=r1){
20         ans = max(ans,sum-solve(l1+1,r1,l2,r2));
21         ans = max(ans,sum-solve(l1,r1-1,l2,r2));
22     }
23     if(l2<=r2){
24         ans = max(ans,sum-solve(l1,r1,l2+1,r2));
25         ans = max(ans,sum-solve(l1,r1,l2,r2-1));
26     }
27     return dp[l1][r1][l2][r2] = ans;
28 }
29 
30 int main(){
31     int T; scanf("%d",&T);
32     while(T--){
33         memset(dp,-1,sizeof(dp));
34         memset(a,0,sizeof(a));
35         memset(b,0,sizeof(b));
36         int n; scanf("%d",&n);
37         for(int i=1; i<=n; i++){
38             scanf("%d",&a[i]);
39             a[i] += a[i-1];
40         }
41         for(int i=1; i<=n; i++){
42             scanf("%d",&b[i]);
43             b[i] += b[i-1];
44         }
45 
46         cout << solve(1,n,1,n) << endl;
47     }
48 }