题解 P4262 【[Code+#3]白金元首与莫斯科】

· · 题解

这篇题解的思路和部分代码实现参考了这篇博客

挺好的题，洛谷上居然没有题解

1 解题思路

题目要求是把每一个格子作为障碍点的时候有多少种方案可以在非障碍点放任意多个 1\times 2 的类似骨牌的东西。

骨牌覆盖问题很容易想到插头dp（大雾

我们令 f_{i,j,st} 表示当前决策的格子是 (i,j)，并且插头状态 st 的方案数。

接下来就是喜闻乐见的大力分类讨论时间：

1、当前格子是障碍点：

这种情况下，只有当前情况下没有下插头和右插头时成立，并且直接可以转移。

2、当前格子不是障碍点且没有下插头也没有右插头：

这时，你有三种选择：
不创建任何插头。
新建一个下插头。
新建一个右插头。

（非常的简单易懂）

3、当前格子有一个下插头或一个右插头：

直接删去插头即可。

4、当前格子有一个下插头和一个右插头：

这种状态是不合法的，因为你只能用 1\times 2 的骨牌覆盖。

接下来，枚举每个点作为障碍点，都做一遍上述的插头dp。

时间复杂度：O(n^2m^22^m) ，再一看数据范围，复杂度直接爆炸。

于是我们就要想着去优化这个算法 （废话）。

2 优化

这个时候其实我也不知所措，于是我去看了上面那位巨佬的博客，发现可以再倒着做一遍上述的插头dp

最后，再枚举障碍点，合并一波答案

怎么合并答案呢？我们来看一张图：

其中，蓝线表示正着dp的轮廓线，绿线表示反着dp的轮廓线

我们发现蓝线和绿线在当前格子处的两个插头都不能有（把当前格子作为障碍点）

接下来，我们又发现任意一个地方正着做的时候有一个下插头，那么对应的反着做的时候就会对应有一个下插头。

于是，我们只要合并两个一样的状态就好了。

时间复杂度：O(nm2^m)

最后，这题最好开一下O2，否则后面几个点可能会RE或者TLE

如果开了O2还TLE，那可以卡卡常

但是现在应该没有必要卡常了，因为本题的时限扩大了200ms

3 代码

还有什么不懂的直接看代码吧qwq

#include<bits/stdc++.h>
#define MAXN 18
#define p 1000000007
using namespace std;
int n,m,ma[20][20];
int f[MAXN][MAXN][270000];
int g[MAXN][MAXN][270000];
int ans[20][20];
void modify(int &a,int b)//卡常，用%的话会变慢
{
    a+=b;
    if(a>p)a-=p;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&ma[i][j]),ma[i][j]^=1;
    int max_state=(1<<m+1)-1;
    f[0][m][0]=1;
    for(int i=1;i<=n;i++)//正着dp
    {
        for(int j=0;j<=max_state;j++)modify(f[i][0][j<<1],f[i-1][m][j]);//转移这一行的初始状态
        for(int j=1;j<=m;j++)
            for(int k=0;k<=max_state;k++)
            {
                int val=f[i][j-1][k];
                if(!val)continue;
                int pl1=(k>>j-1)&1;//右插头
                int pl2=(k>>j)&1;//下插头
                if(!ma[i][j]){if(!pl1&&!pl2)modify(f[i][j][k],val);}//第一种情况
                else if(!pl1&&!pl2)//第二种情况
                {
                    modify(f[i][j][k],val);
                    if(ma[i+1][j])modify(f[i][j][k^(1<<j-1)],val);
                    if(ma[i][j+1])modify(f[i][j][k^(1<<j)],val);
                }
                else if(!pl1&&pl2)//第三种情况
                    modify(f[i][j][k^(1<<j)],val);
                else if(pl1&&!pl2)//第三种情况
                    modify(f[i][j][k^(1<<j-1)],val);
            }
    }
    g[n+1][1][0]=1;
    for(int i=n;i>0;i--)//反着dp与正着dp同理，反过来就好了
    {
        for(int j=0;j<=max_state;j++)modify(g[i][m+1][j>>1],g[i+1][1][j]);
        for(int j=m;j>0;j--)
            for(int k=0;k<=max_state;k++)
            {
                int val=g[i][j+1][k];
                if(!val)continue;
                int pl1=(k>>j-1)&1;
                int pl2=(k>>j)&1;
                if(!ma[i][j]){if(!pl1&&!pl2)modify(g[i][j][k],val);}
                else if(!pl1&&!pl2)
                {
                    modify(g[i][j][k],val);
                    if(ma[i-1][j])modify(g[i][j][k^(1<<j)],val);
                    if(ma[i][j-1])modify(g[i][j][k^(1<<j-1)],val);
                }
                else if(!pl1&&pl2)
                    modify(g[i][j][k^(1<<j)],val);
                else if(pl1&&!pl2)
                    modify(g[i][j][k^(1<<j-1)],val);
            }
    }
    for(int i=1;i<=n;i++)//合并答案
        for(int j=1;j<=m;j++)
        {
            if(!ma[i][j])continue;
            int now=max_state^(1<<j-1)^(1<<j);//合法状态
            for(int k=now;k;k=(k-1)&now)//取合法状态的所有子集
                modify(ans[i][j],1ll*f[i][j-1][k]*g[i][j+1][k]%p);
            modify(ans[i][j],1ll*f[i][j-1][0]*g[i][j+1][0]%p);//0也是合法状态
        }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",ans[i][j]);//输出即可
        puts("");
    }
    return 0;
}