首页 > 代码库 > hdu 4597 Play Game

hdu 4597 Play Game

2024-07-18 18:44:57   218人阅读

Play Game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 664    Accepted Submission(s): 394


Problem Description
Alice and Bob are playing a game. There are two piles of cards. There are N cards in each pile, and each card has a score. They take turns to pick up the top or bottom card from either pile, and the score of the card will be added to his total score. Alice and Bob are both clever enough, and will pick up cards to get as many scores as possible. Do you know how many scores can Alice get if he picks up first?
 

 

Input
The first line contains an integer T (T≤100), indicating the number of cases. 
Each case contains 3 lines. The first line is the N (N≤20). The second line contains N integer ai (1≤ai≤10000). The third line contains N integer bi (1≤bi≤10000).
 

 

Output
For each case, output an integer, indicating the most score Alice can get.
 

 

Sample Input
2
 
 
1
23
53
 
3
10 100 20
2 4 3
 

 

Sample Output
53
105
 
Source
2013 ACM-ICPC吉林通化全国邀请赛——题目重现
 

 

Recommend
liuyiding
 
 
解题：dp[fr1][ta1][fr2][ta2]表示第一叠牌第一张是fr1,最后一张是ta1,第二叠牌，第一张是fr2,最后一张是ta2。
 
fr1 <= ta1 时有两种选择，可以选择第一叠牌上面的，第一叠牌下面的。假设自己选择上面的，那么有
 
theMax = max(theMax,sum-dfs(fr1+1,ta1,fr2,ta2,sum-a[fr1]));
sum表示当前剩下的牌数和，当前选a[fr1]牌，剩下的给后者选，sum-后者选的，剩下的就是先者所得的值。
 
 
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 int n,a[24],b[24],dp[24][24][24][24];18 int dfs(int fr1,int ta1,int fr2,int ta2,int sum){19     if(fr1 > ta1 && fr2 > ta2) return 0;20     if(dp[fr1][ta1][fr2][ta2]) return dp[fr1][ta1][fr2][ta2];21     int theMax = 0;22     if(fr1 <= ta1){23         theMax = max(theMax,sum-dfs(fr1+1,ta1,fr2,ta2,sum-a[fr1]));24         theMax = max(theMax,sum-dfs(fr1,ta1-1,fr2,ta2,sum-a[ta1]));25     }26     if(fr2 <= ta2){27         theMax = max(theMax,sum-dfs(fr1,ta1,fr2+1,ta2,sum-b[fr2]));28         theMax = max(theMax,sum-dfs(fr1,ta1,fr2,ta2-1,sum-b[ta2]));29     }30     return dp[fr1][ta1][fr2][ta2] = theMax;31 }32 int main() {33     int t,sum,i;34     scanf("%d",&t);35     while(t--){36         scanf("%d",&n);37         for(i = 1; i <= n; i++){38             scanf("%d",a+i);39             sum += a[i];40         }41         for(i = 1; i <= n; i++){42             scanf("%d",b+i);43             sum += b[i];44         }45         memset(dp,0,sizeof(dp));46         printf("%d\n",dfs(1,n,1,n,sum));47     }48     return 0;49 }
View Code

 


联系
我们