[NOI2018省队选拔赛]一双木棋 题解【博弈】【状压DP】【记忆化搜索】

作者: wjyyy 分类: DP,博弈,搜索,数学,状态压缩,解题报告,记忆化搜索 发布时间: 2018-07-06 09:12

点击量:179

考试的时候什么都不知道。。。

 

【题面】

 

   题目的关键在于

 

   如何保证状态合法,也就是棋子必须保证被下在一个矩形的右下角,像这样

   也就是说,一个棋子能被下在右下角这个位置,左上边所有被标记的点都必须已经被下过了。因此我们引入了状压轮廓线,来存储棋盘当前的状态。

 

   因为n,m≤10,所以轮廓线长度不超过20,在上图中我们设横着的轮廓线为0,竖着的轮廓线为1,那么轮廓线就是11101000(从第0位到第7位是从左下到右上)。不难看出,能下棋子的地方就是有序连续数对10(表示上凸)所处的位置。我们从(n+1,1)开始推,遇到0向右,纵坐标+1,遇到1向上,横坐标-1。

 

   对于轮廓线$ x$,因为有左上限制,所以有唯一棋子摆放方式与之对应,同时可以判断出当前唯一玩家是菲菲Alice还是牛牛Bob,当轮廓线框住奇数时,就是Bob,当轮廓线框住偶数时,就是Alice,这一点我们可以通过0与1的逆序对个数来求,因为一旦出现一个0,说明轮廓向右,则这一个横轮廓上面所有的格子一定都被填充满了。以此类推,就能判断出轮廓线对应唯一玩家和唯一摆放方式。证明出这个就为我们的DP打下基础。

 

   上面提到了,每个轮廓线可以从有序连续数对01扩展出去,而我们并没有后面的状态,那么我们可以尝试进行记忆化搜索,来找到后面的状态,继续更新。因为如果当前轮廓线被搜索过,再次搜索它之前一定已经把后面的状态处理完了,状态又比较多,那么直接调用结果就可以了。最后在所有可转移出去的结果回溯回来时取最优值(对两个人来说最优值不同,Alice使差值totA-totB尽可能大,Bob使差值totA-totB尽可能小),就演变成了一种DP,f[轮廓线]表示使差值尽量满足当前轮廓线对应玩家的最优解,实则还是记忆化搜索。

 

   每次搜索时可以带两个参数,p和z,分别表示当前是Alice还是Bob和轮廓线。因为每次判断轮廓线太耗时,而每次对p取反又很方便,所以直接多带个参数。

 

   对最优策略的理解:这个题要求都采取在知道对方采取最优策略的情况下采取最优策略,所以我们进行dfs,返回的状态就是从这里搜索返回的最优策略下的答案。因为当一次搜索函数回退时,一定已经找到了右下角的终态。右下角最后一个人只有一种方案,则一定是最优,而上溯一层,发现有两种方案可以被转移,就根据最后一格的最优解,更新每一格的最优解,最终每个人考虑到后面另一个人考虑自己的最优解时的最优解,每次都这样,运用DP的思想,答案就是符合要求的。

 

Code:

#include<cstdio>
#include<cstring>
int min(int x,int y)
{
    return x<y?x:y;
}
int max(int x,int y)
{
    return x>y?x:y;
}
int f[1050000];
int n,m;
int a[12][12],b[12][12];
bool used[1050000];//因为状态有正有负,所以不合法状态用!used来判
int dfs(bool p,int z)
{
    if(used[z])
        return f[z];
    int t=z;//不要把t和z搞混了
    if(!p)
    {
        int i=n+1,j=1;
        for(int k=1;k<n+m;k++)
        {
            if(t&1)
                i--;
            else
                j++;
            if(((t&1)==1)&&((t&2)==0))//10是上凸
            {
                if(used[z])
                    f[z]=min(f[z],dfs(p^1,z^(3<<(n-i+j-1)))-b[i][j]);//z的转移是把11挪到改变的位置做异或
                else
                {
                    f[z]=dfs(p^1,z^(3<<(n-i+j-1)))-b[i][j];
                    used[z]=true;
                }
            }

            t>>=1;
        }
    }
    else
    {
        int i=n+1,j=1;
        for(int k=1;k<n+m;k++)
        {
            if(t&1)
                i--;
            else
                j++;
            if(((t&1)==1)&&((t&2)==0))
            {
                if(used[z])
                    f[z]=max(f[z],dfs(p^1,z^(3<<(n-i+j-1)))+a[i][j]);
                else
                {
                    f[z]=dfs(p^1,z^(3<<(n-i+j-1)))+a[i][j];
                    used[z]=true;
                }
            }
            t>>=1;
        }
    }
    return f[z];
}
int main()
{
    memset(used,0,sizeof(used));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&b[i][j]);
    used[(1<<(n+m))-(1<<(n))]=0;//最终状态
    int t=1<<n;
    t--;
    printf("%d\n",dfs(1,t));
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */