[NOI2018省队选拔赛]一双木棋 题解【博弈】【状压DP】【记忆化搜索】
点击量: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;
}
说点什么