首页 > 代码库 > UVa 10891 Sum游戏
UVa 10891 Sum游戏
https://vjudge.net/problem/UVA-10891
题意：
有一个长度为n的整数序列，两个游戏者A和B轮流取数，A先取。每次玩家只能从左端或者右端取任意数量个数，但不能两端都取。所有数都被取走后游戏结束，然后统计每个人取走的所有数之和，作为各自的得分。两个人采取的策略都是让自己的得分尽量高，并且两个人都足够聪明，求A的得分减去B的得分后的结果。
思路:
不管是轮到谁取数，都是在一个序列中从左边或右边开始取最大值。
那么我们就令d【i】【j】表示先手在【i~j】序列中所能取到的最大值。
状态转移时，枚举从左端开始取k个数和从右端开始取k个数即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 using namespace std;12 typedef long long LL;13 typedef pair<int,int> pll;14 const int INF=0x3f3f3f3f;15 const int maxn=100+5;16 17 int n;18 int a[maxn];19 int sum[maxn];20 int vis[maxn][maxn];21 int d[maxn][maxn];22 23 int dp(int i,int j)24 {25 if(vis[i][j]) return d[i][j];26 vis[i][j]=1;27 28 int m=0;29 for(int k=i+1;k<=j;k++) m=min(m,dp(k,j));30 for(int k=j-1;k>=i;k--) m=min(m,dp(i,k));31 d[i][j]=sum[j]-sum[i-1]-m;32 return d[i][j];33 }34 35 int main()36 {37 //freopen("D:\\input.txt","r",stdin);38 while(~scanf("%d",&n) && n)39 {40 sum[0]=0;41 for(int i=1;i<=n;i++)42 {43 scanf("%d",&a[i]);44 sum[i]=sum[i-1]+a[i];45 }46 47 memset(vis,0,sizeof(vis));48 printf("%d\n",2*dp(1,n)-sum[n]);49 }50 return 0;51 }
UVa 10891 Sum游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。