无限UCW

[题解]洛谷P2734:游戏 A Game
原题链接:P2734 游戏 A Game本题的大体思路是很明确的,初见有点Nim游戏的意思(当然似乎也能用博弈论搞...
扫描右侧二维码阅读全文
02
2019/02

[题解]洛谷P2734:游戏 A Game

原题链接:P2734 游戏 A Game


本题的大体思路是很明确的,初见有点Nim游戏的意思(当然似乎也能用博弈论搞,只是我太弱了,区间DP都要写一下午),审过之后发现是个比较容易想到的区间dp,只是我的方程似乎和题解的不太一样。

这道题有一点非常迷,就是你初见很难看懂它想让你干什么,一旦审错就会GG,收不了。这可能是翻译的锅,毕竟原题出自USACO,洛谷评级为绿题(普及+/提高),我觉得比较客观。

看一下题目中的描述:

编一个执行最优策略的程序,最优策略就是使玩家在与最好的对手对弈时,能得到的在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。

哦豁,完蛋,本来你不说可能能看懂的说了也开始迷了。

其实它的意思就是两边都执行最优策略,也就是Nim的搞法。为什么呢?最优策略定义为使玩家在与最好的对手对弈时,能得到的在当前情况下最大的可能的总分的策略,保证了对手策略最优,因为要与“最好的对手”对弈,肯定对方不可能放水,而“为第二位玩家执行最优策略”则意味着第二位也不能随便乱骚,这样一来我们的方向就确定了:双方都执行全局最优解

编写程序时,要同时为双方规划全局最优策略。


有了切入点之后,稍作分析不难发现:设f[i][j]为第一个游戏者在闭区间[i,j]中所能得到的最大得分,则状态转移方程可表示为:
f[i][j]=(((j-i)&1)==!ep)?max(f[i+1][j]+a[i],f[i][j-1]+a[j]):min(f[i+1][j],f[i][j-1])
其中ep=N&1已事先计算好,且在整个过程中不改变。

简单解释一下,ep是我设置的一个奇偶标志,因为如果按照我的思路设计状态,N的奇偶势必会对f[i][j]的计算造成影响,若N为奇数即ep=N&1=1,则对于每个区间长度j-i+1为奇数的状态,均是第一个游戏者取数的状态,而区间长度为偶数则是第二个游戏者取数,无需进行累加(想一想,为什么?)。

另外,上述状态转移方程其实是化简后的结果,所以有必要进行详细说明。参考下面这个dp函数:

int dp(int i,int j){
    if(i==j)return ep?sum(i,i):0;
    if(f[i][j])return f[i][j];
    if(((j-i)&1)==!ep){//第一个游戏者取数
        //为什么必须是"==!ep"?
        //"==ep"有什么问题呢?
        //因为(j-i)并不是闭区间[i,j]的长度,(j-i+1)才是。若写作"((j-i+1)&1)==ep",那么这个条件将会是正确的。
        f[i][j]=max(dp(i+1,j)+sum(i,i),dp(i,j-1)+sum(j,j));
    }else{//第二个游戏者取数
        //他们都取全局最优解,所以进行计算。
        int l=dp(i+1,j),r=dp(i,j-1);
        //int ss=sum(i,j); 假设ss为闭区间[i,j]的总和,l和r分别为[i+1,j]和[i,j-1]中第一个游戏者的最大得分
        if(l<r){//ss-l>ss-r 显见,总和-其中一个得分=另一个的得分,因为数必须取完,化简得min(dp(i+1,j),dp(i,j-1))
            f[i][j]=l;
        }else{
            f[i][j]=r;
        }
    }
    return f[i][j];
}

参考代码注释中的分析,得到简化后的dp函数:

int dp(int i,int j){
    if(i==j)return ep?a[i]:0;//*important
    if(f[i][j])return f[i][j];
    return f[i][j]=(((j-i)&1)==!ep)?max(dp(i+1,j)+a[i],dp(i,j-1)+a[j]):min(dp(i+1,j),dp(i,j-1));
}

简洁优美。其中i==j的特判是为了规避初始化的窘境,这一点我没能想到更好的解决方案,需要注意。

改成递推计算:

scanf("%d",&N);
ep=N&1;//根据N的奇偶决定计算方式。 
int tot=0;//存一个总和,便于计算第二个游戏者的得分。 
for(register int m=1;m<=N;m++)scanf("%d",&a[m]),tot+=a[m];
//f[i][j]依赖于f[i+1][j]和f[i][j-1],所以我们可以递推处理。 
//但对每次循环a[i]与a[j]都是必须的,故无法边读边计算。 
//使用滚动数组可节约空间,O(n^2)优化至O(n)。 
for(register int i=N;i>=1;i--){
    for(register int j=1;j<=N;j++){
        if(i==j)f[j]=ep?a[i]:0;
        else f[j]=(((j-i)&1)==!ep)?max(f[j]+a[i],f[j-1]+a[j]):min(f[j],f[j-1]);
    }
}
printf("%d %d",f[N],tot-f[N]);

就是如此简单√ ->R16029924


一个常数优化:考虑第二重循环,j根本不必从1开始枚举,因为我们规定ij分别是区间[i,j]下界和上界,即满足$i \leq j$,j可以从i开始枚举,可以优化常数。
而且,这样一来的话,循环中的if语句也不再必要(想一想,为什么?),代码更加简洁:

for(register int i=N;i>=1;i--){
    for(register int j=i;j<=N;j++){
        f[j]=(((j-i)&1)==!ep)?max(f[j]+a[i],f[j-1]+a[j]):min(f[j],f[j-1]);
    }
}

分析i==j时的情况,此时((j-i)&1)==!ep等价于0==!ep,即条件退化为ep?(...):(...),已知ep?a[i]:0是正确的结论,根据计算顺序,j枚举的范围[i,N]右端点固定,左端点逐渐左移,当i==jf[j]尚未计算(因为若此时不是第一次循环,上次计算的范围是[i+1,N];而如果此时是第一次循环的话计算尚未开始),初始化f[j]=0i从大到小枚举,f[j]都尚未计算f[j-1]更不可能已经算过。故此时max(f[j]+a[i],f[j-1]+a[j])直接化简为max(a[i],a[j]),是同一个数a[i]min(f[j],f[j-1])参考前面的分析可化为min(0,0)=0,此时的方程与f[j]=ep?a[i]:0等价。

最后修改:2019 年 02 月 03 日 10 : 51 AM

发表评论