NYIST 1030 Yougth's Game[Ⅲ]

Yougth's Game[Ⅲ]
时间限制：3000 ms | 内存限制：65535 KB
难度：4

描述
有一个长度为n的整数序列，A和B轮流取数，A先取，每次可以从左端或者右端取一个数，所有数都被取完时游戏结束，然后统计每个人取走的所有数字之和作为得分，两人的策略都是使自己的得分尽可能高，并且都足够聪明，求A的得分减去B的得分的结果。

输入
输入包括多组数据，每组数据第一行为正整数n（1<=n<=1000）,第二行为给定的整数序列Ai（-1000<=Ai<=1000）。

输出
对于每组数据，输出A和B都采取最优策略的情况下，A的得分减去B的得分的结果。

样例输入
3
1 2 3
4
2 4 5 3

样例输出
2
0

来源
Yougth原创

上传者
TC_杨闯亮

解题：dp题，dp[i][j]表示在剩下i到j时的最优结果，由于双方都采取最优策略，dp[a][b] = max(sum - dfs(a+1,b,sum-d[a]),sum - dfs(a,b-1,sum-d[b]))

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 int dp[maxn][maxn],d[maxn],n;

 int dfs(int a,int b,int sum){

     if(a > b) return ;

     if(dp[a][b]) return dp[a][b];

     dp[a][b] = max(sum - dfs(a+,b,sum-d[a]),sum - dfs(a,b-,sum-d[b]));

     return dp[a][b];

 }

 int main() {

     while(~scanf("%d",&n)){

         int sum = ;

         for(int i = ; i <= n; ++i){

             scanf("%d",d+i);

             sum += d[i];

         }

         memset(dp,,sizeof(dp));

         int ans = dfs(,n,sum);

         printf("%d\n",*ans-sum);

     }

     return ;

 }

 /*

 */

巴特西

NYIST 1030 Yougth's Game[Ⅲ]

最新文章

热门文章