题解 UVA10891 Game of Sum

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