UVA10891 Game of Sum
题目描述
有一个长度为n的整数序列,两个游戏者A和B轮流取数,A先取。每次玩家只能从左端或者右端取任意数量的数,但不能两边都取。所有数都被取走视为游戏结束,然后统计每个人取走的数之和,作为各自的得分。两个人采取的策略都是让自己得分尽可能高,并且两个人都很机智,求A得分-B得分后的结果。
输入包含多组数据,每组数据第一行为正整数n(1<=n<=100) ,第二行为给定的整数序列,输入结束标志是n=0
对于每组数据,输出A和B都采取最优策略下,A的得分-B的得分
感谢刘汝佳
总和一定,每个数都要取,设A得分为A,B得分为B,A+B=SUM
我们DP算出i-j段A取的最大值,在维护一个前缀和,即可求出B的得分
一个人取完一段后,删掉这段,就生成了新的一个序列
思考一下,一个序列不断删左删右生成新序列,序列中间的值不变,故可以从小序列转移到大序列,故此题是一个区间DP
再思考一下,我们只用算出每一个区间的最优先手值
即取区间l-r的第一个人能得到的最大得分
如果i-r或者l-k是l-r的子区间,那么找到包含l-r最小子区间的最优先手值
用此区间的值减去最小子区间的最优先手值,即可得到该区间的最优先手值
为什么是这样呢?
对于一个区间,每个值都要取走,那么说明每个子区间也必须取走
对于这个区间,我们取走的是一个子区间,这个子区间的总值就是最优先手值
另一个子区间,也如此
这样就可以保证每一次都取到最优先手值
代码
#include<bits/stdc++.h>
int a[200],sum[200],n;
int dp[200][200];
int main (){
while(scanf("%d",&n)&&n!=0){
memset(sum,0,sizeof(sum)) ;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),dp[i][i]=a[i],sum[i]=sum[i-1]+a[i];
for(int i=1;i<n;++i){//长度
for(int l=1;l<=n&&l+i<=n;++l){
int r=l+i,temp=999999999;
for(int k=l;k<=r;k++)
temp=std::min(dp[l][k],temp);//算出子区间最小的最优先手值
for(int k=l;k<=r;k++)
temp=std::min(temp,dp[k][r]);//可以优化,递推出区间最小的最优先手值
dp[l][r]=sum[r]-sum[l-1]-temp;
}
}
printf("%d\n",dp[1][n]-(sum[n]-dp[1][n]));
}
}
0 条评论