P10975 Mondriaan's Dream 轮廓线 dp 题解

· · 题解

题意

用大小为 1 \times 2 和 2 \times 1 的小矩形填充一个 h \times w 的大矩形，求方案数。

思路

一眼状压 dp，注意到可以维护 dp_{i,S} 表示目前枚举到第 i 行，且第 i 行的填充状态为 S，预处理判断合法状态以及合法转移即可，时间复杂度 O(h \times 4^w)。

这个时候就有人问了，主播主播，状压 dp 确实很强，但状态转移还是太吃操作了，有没有更加简单又强势的算法推荐一下吗？有的兄弟，有的。

这个时候我们引出轮廓线 dp，也就是所谓的插头 dp。

说一下轮廓线 dp 的一些定义。

我们假定绿色格子为已决策格子。

轮廓线：已决策格子和没决策格子的分界线，也就是图中黑线。

插头：一个格子某个方向的插头存在表示这个格子在这个方向与相邻格子相连，因此，一个格子有四个插头，分别在上下左右。

轮廓线上方与其相连的有 n+1 个插头，包括 n 个下插头和 1 个右插头，也就是图中灰色部分。

由于这道题不需要考虑连通性，所以也不需要学到最小表示法，每个插头只需要用 0 或 1 表示，所以维护轮廓线上方的插头状态二进制压缩存储即可。

举一个这道题的例子，其中灰色插头为 0，表示不需要与之前的状态产生联系，红色插头为 1，表示需要和之前的状态拼成一个 1 \times 2 矩形。

枚举到当前状态时，因为左侧有一个 1 的插头，所以只有一种转移，也就是把表示当前的方格与左侧组成 1 \times 2 矩形，此时的状态需要把左侧的 1 插头变为 0 插头。

对于这道题而言，一共有四种情况。

  1. 左侧为 1，上方为 1。

这种状态不符合条件，不产生贡献。

  1. 左侧为 1，上方为 0。

把左侧的 1 插头变为 0 插头。

  1. 左侧为 0，上方为 1。

把上方的 1 插头变为 0 插头。

  1. 左侧为 0，上方为 0。

这个时候有两种情况，第一种是向下转移，将下方 0 插头变为 1 插头，第一种是向右转移，将右侧 0 插头变为 1 插头。

最后统计贡献即可，时间复杂度 O(hw \times 2^w)。

转移细节

在枚举到行末之后，要进行下一行的枚举，所以要将状态左移一位。（注意最右侧插头若为 1 则删除该状态）

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define mkp make_pair
const int N=10024,M=16;
int t,n,m,cur;
int a[M][M],f[2][N];
int get(int stt,int k){
    return (stt>>k)&1;
}
int calc(int k,int v){
    return v*(1<<k);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n>>m){
        if(n==0&&m==0){
            break;
        }
        cur=0;
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for(int i=1;i<=n;i++){
            cur^=1;
            memset(f[cur],0,sizeof(f[cur]));
            for(int j=0;j<(1<<m);j++){
                f[cur][j<<1]=f[cur^1][j];
            }
            for(int j=1;j<=m;j++){
                cur^=1;
                memset(f[cur],0,sizeof(f[cur]));
                for(int st=0;st<(1<<(m+1));st++){
                    if(!f[cur^1][st]) continue;
                    int x=get(st,j-1),y=get(st,j);
                    if(x && y){
                        continue;
                    }
                    else if(x){
                        f[cur][st-calc(j-1,1)]+=f[cur^1][st];
                    }
                    else if(y){
                        f[cur][st-calc(j,1)]+=f[cur^1][st];
                    }
                    else{
                        f[cur][st+calc(j-1,1)]+=f[cur^1][st];
                        f[cur][st+calc(j,1)]+=f[cur^1][st];
                    }
                }
            }
        } 
        cout<<f[cur][0]<<"\n";
    }
    return 0;
}