题解 UVA10891 Game of Sum

作者: MayFlyyh 分类: DP 发布时间: 2018-03-10 13:03 ė 6 没有评论

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]));
    }
} 

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/166

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部