轮廓线 dp

也叫插头 $\text{dp}$ ，大部分时间叫插头 $\text{dp}$ 多一些，毕竟字少。

给定一个二维平面，让你填数，如果我们一次要用到一行信息，那我们枚举本行和下行状态就要达到 $\Theta(4^{\min(n,m)}\max(n,m))$ 。

但如果我们只记录轮廓线上的信息，复杂度就降低为 $\Theta(2^{\min(n,m)}nm)$ ，有时候也适用于一维极大一维极小的情况。

上例题：

UVA11270 Tiling Dominoes

$n\times m$ 的棋盘，摆 $1\times 2$ 的多米诺骨牌，问有多少方案。

$n\times m\le 100$ 。

其实插头 $\text{dp}$ 并不一定要记录每个点上的具体信息，而是为了实际而服务。

填东西也不一定到了一个格就必须填，也是可以暂定空着的。

比如说这个题你并不需要记录轮廓线上的每个点是上下左右部分，只需要记录填了还是没填。

横放的条件是左部为空，上部非空。

竖放的条件是上部为空。

空着的条件是上部非空。

memset(f,0,sizeof f);f[(1<<m)-1]=1;
F(i,1,n) F(j,1,m) {
    F(B,0,(1<<m)-1){
        if(j!=1&&(B>>j-1&1)&&!(B>>j-2&1)) g[B|1<<j-1|1<<j-2]+=f[B];
        if(!(B>>j-1&1)) g[B|1<<j-1]+=f[B];
        if(B>>j-1&1) g[B^(1<<j-1)]+=f[B];
    } memcpy(f,g,sizeof f);memset(g,0,sizeof g);
} printf("%lld\n",f[(1<<m)-1]);

P5074 Eat the Trees

$n \times m$ 的方格，有些格子不能铺线，其它格子必须铺，可以形成多个闭合回路，计数。

$n,m\le 12$ 。

只需要关心每个位置是否有下插头，以及左边有无右插头。

分讨：

F(i,1,n) F(j,1,m) can[i][j]=read();
memset(f,0,sizeof f);
f[0]=1;F(i,1,n) F(j,1,m) {
    F(B,0,(1<<m+1)-1) if(can[i][j]) {
        if(B>>j-1&1 and B>>m&1) g[B^1<<m^1<<j-1]+=f[B];//lu
        if(!(B>>j-1&1) and B>>m&1) 
            j!=m&&(g[B]+=f[B]),//lr
            g[B^1<<m^1<<j-1]+=f[B];//ld
        if(B>>j-1&1 and !(B>>m&1)) 
            g[B]+=f[B],//ud
            j!=m&&(g[B^1<<m^1<<j-1]+=f[B]);//ru
        if(!(B>>j-1&1) and !(B>>m&1)) j!=m&&(g[B^1<<m^1<<j-1]+=f[B]);//rd
    } else {
        if(!(B>>j-1&1) and !(B>>m&1)) g[B]+=f[B];//nothing
    } memcpy(f,g,sizeof g);memset(g,0,sizeof g);
} cout<<f[0]<<endl;

要注意的是最后一列就不能放右插头了。

Gym103446C Strange Matrices

给定一个棋盘，上面有 $0/1/2$ ，你需要把每个 $2$ 换成 $0/1$ ，使得以下权值最小：

选出一些 $0$ 的位置，在上面放置十字炸弹，不能穿透 $1$ ，要求炸到所有的 $0$ 位置，该方案的权值是选出的 $0$ 位置个数。

可以做到 $n\times m\le 190$ （NFLS 2024.1.15）。

如果 $2$ 被炸弹炸到那么一定选 $0$ （可以提高炸弹通透程度），否则一定选 $1$ ，所以 $2$ 可以看作可以不用被轰炸的 $0$ 。

你发现你只关心纵向轰炸，所以每个位置只有三种情况：钦定被纵向轰炸而被纵向轰炸了，钦定而没被纵向轰炸，未钦定。

看上去似乎很难处理横向的炸弹，实际上我们只需要记录拐点处是否被横向炸到即可。

复杂度 $\Theta(nm3^{\min(n,m)+1})$ 。

对于这种有很多不合法情况的轮廓线 $\text{dp}$ ，我们很多时候会采用 unordered_map 或者 vector 记录合法位置的写法。

unoredered_map 有更大的好处，那就是三进制可以当四进制写，提前处理 a[i]=2*i，想访问 0,1 就使用 1<<a[i]，想访问 2,3 就使用 2<<a[i]，或者说你不必区分各种状态，你只需要管是否钦定，以及是否攻击，去重和合法性会由程序帮你完成。

如果有侧向状态的记录，常用的方式并不是记在最后一位，而是记在第 j 位，即该位置的下方状态右边，在每行末尾处再把所有状态都左移 1 位，这样 S>>j-1&1 就是左方侧向状态，S>>j&1 就是上方状态，填数就把上方状态和侧向状态填到 S>>j-1&1 和 S>>j&1 即可。

注意，在这种记录方式下即使你还想沿用同样的上方状态和侧向状态，你也需要将它们调换位置，而不是什么也不干，优秀的处理方式通常是先把 S 中这两位清空，再一点一点添加。

代码。