首页 > 代码库 > NYIST 1030 Yougth's Game[Ⅲ]
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]))
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 const int maxn = 1002;18 int dp[maxn][maxn],d[maxn],n;19 int dfs(int a,int b,int sum){20 if(a > b) return 0;21 if(dp[a][b]) return dp[a][b];22 dp[a][b] = max(sum - dfs(a+1,b,sum-d[a]),sum - dfs(a,b-1,sum-d[b]));23 return dp[a][b];24 }25 int main() {26 while(~scanf("%d",&n)){27 int sum = 0;28 for(int i = 1; i <= n; ++i){29 scanf("%d",d+i);30 sum += d[i];31 }32 memset(dp,0,sizeof(dp));33 int ans = dfs(1,n,sum);34 printf("%d\n",2*ans-sum);35 }36 return 0;37 }38 /*39 40 */
NYIST 1030 Yougth's Game[Ⅲ]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。