題干：

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 a?i?(1≤a?i≤10000). The third line contains N integer b?i?(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

題目大意：

Alice和Bob玩一個游戲，有兩個長度為N的正整數(shù)數(shù)字序列，每次他們兩個只能從其中一個序列，選擇兩端中的一個拿走。他們都希望可以拿到盡量大的數(shù)字之和，并且他們都足夠聰明，每次都選擇最優(yōu)策略。Alice先選擇，問最終Alice能拿到的數(shù)字總和是多少？

解題報告：

直接dp[][][][]就行了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 20 + 5; int dp[MAX][MAX][MAX][MAX],sa[MAX],sb[MAX]; int a[MAX],b[MAX]; int n,sum; int dfs(int l,int r,int L,int R) {if(dp[l][r][L][R] != -1) return dp[l][r][L][R];int res = 0;int ssum = sa[r]-sa[l-1] + sb[R]-sb[L-1];if(l<=r) res = max(res,ssum - dfs(l+1,r,L,R)),res = max(res,ssum - dfs(l,r-1,L,R));if(L<=R) res = max(res,ssum - dfs(l,r,L+1,R)),res = max(res,ssum - dfs(l,r,L,R-1));return dp[l][r][L][R] = res; } int main() {int t;cin>>t;while(t--) {scanf("%d",&n);sum=0;memset(dp,-1,sizeof dp);for(int i = 1; i<=n; i++) scanf("%d",a+i),sum += a[i],sa[i] = sa[i-1] + a[i];for(int i = 1; i<=n; i++) scanf("%d",b+i),sum += b[i],sb[i] = sb[i-1] + b[i];printf("%d\n",dfs(1,n,1,n));} return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 4597】Play Game（博弈dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。