学习心得 - 动态规划 - 插头 DP

· · 算法·理论

唉很久以前初学状态压缩 DP 留下的巨坑，填填。

什么是插头 DP

基于连通性状态压缩的动态规划问题。

%%% cdq 巨佬。

一般是求回路数量的。

什么是插头

如图。

一个蓝色方格有四个插头，就是指向相邻节点的插头。

我们求答案就是通过这些插头求的。

例如回路，我们就可以通过处理这些插头，让他们连成一个回路，来求解。

我们依据这些插头的存在求出答案。

怎么 DP

我们设 f_{i,j,s} 为当前 i,j 的状态 s 所能计算出的答案。

我们发现 n,m\leq 12 这些特别小的数。

通常考虑状压。

我们发现逐个转移的 DP 会把棋盘分为两半。

然后这个边界就是轮廓线。

如图。

这就是为什么插头 DP 又叫轮廓线 DP。

状态

性质：轮廓线两两不相交。

我们发现一个轮廓线上的插头有三个状态：入插头，出插头与无插头。

所以可以转换成三进制。

如图。

那如何编码呢？

我们发现三进制不好写，考虑转成 2^P 进制位运算。通常是 4 进制。

之后直接位运算即可，相信大家都会。

转移

转移方法有很多。

  1. 新建连通分量。
    • 无下插头与右插头。
  2. 合并连通分量。
    • 有下插头与右插头，让他们连通。
  3. 保持连通分量。
    • 只有下插头或右插头，做一个左插头或上插头让他合法。

优化

哈希优化，直接挂表记录相同状态。

预处理每一个插头状态。

DP 代码

#include<bits/stdc++.h>
using namespace std;
const int P=590027,N=6e5+10;
#define ll long long
ll f[2][N],nwans,res;
int sta[2][N],pr,nw,con[30],cur[2],ex,ey;
char ch;
int a[30][30],n,m;
int nwsta,upcon,lecon;
struct node{
    int pr,to;
}id[N];
int nxt[N],ncur;
void insert(int now,ll val){
    int add=now%P;
    for(int i=nxt[add];i;i=id[i].pr){
        if(sta[nw][id[i].to]==now){
            f[nw][id[i].to]+=val;
            return;
        }
    }
    cur[nw]++;
    sta[nw][cur[nw]]=now;
    f[nw][cur[nw]]=val; 
    id[++ncur].pr=nxt[add];
    id[  ncur].to=cur[nw];
    nxt[add]=ncur;
}
void dp(){
    pr=1,nw=0;
    cur[nw]=1;
    f[nw][1]=1;
    sta[nw][1]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cur[nw];j++)sta[nw][j]<<=2;
        for(int j=1;j<=m;j++){
            ncur=0;
            memset(nxt,0,sizeof(nxt));
            swap(pr,nw);
            cur[nw]=0; 
            for(int k=1;k<=cur[pr];k++){
                nwsta=sta[pr][k];
                nwans=  f[pr][k];
                upcon=(nwsta>>con[j])%4;
                lecon=(nwsta>>con[j-1])%4;
                if(!a[i][j]){if((!upcon)&&(!lecon))insert(nwsta,nwans);}
                else if((!upcon)&&(!lecon)){if(a[i+1][j]&&a[i][j+1])insert(nwsta+(1<<con[j-1])+2*(1<<con[j]),nwans);}
                else if((!upcon)&&lecon){
                    if(a[i+1][j])insert(nwsta,nwans);
                    if(a[i][j+1])insert(nwsta-lecon*(1<<con[j-1])+lecon*(1<<con[j]),nwans);
                }else if(upcon&&(!lecon)){
                    if(a[i][j+1])insert(nwsta,nwans);
                    if(a[i+1][j])insert(nwsta-upcon*(1<<con[j])+upcon*(1<<con[j-1]),nwans);
                }else if(upcon==1&&lecon==1){
                    int cnt=1;
                    for(int l=j+1;l<=m;l++){
                        if((nwsta>>con[l])%4==1)++cnt;
                        else if((nwsta>>con[l])%4==2)--cnt;
                        if(!cnt){
                            insert(nwsta-(1<<con[l])-(1<<con[j])-(1<<con[j-1]),nwans);
                            break;
                        }
                    }
                }else if(upcon==2&&lecon==2){
                    int cnt=1;
                    for(int l=j-2;l>=0;l--){
                        if((nwsta>>con[l])%4==1)--cnt;
                        else if((nwsta>>con[l])%4==2)++cnt;
                        if(!cnt){
                            insert(nwsta-2*(1<<con[j])+(1<<con[l])-2*(1<<con[j-1]),nwans);
                            break;
                        }
                    }
                }else if(upcon==1&&lecon==2)insert(nwsta-2*(1<<con[j-1])-(1<<con[j]),nwans);
                else if(upcon==2&&lecon==1){if(i==ex&&j==ey)res+=nwans;}
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        cin>>ch;
        if(ch=='.')a[i][j]=1,ex=i,ey=j;
    }
    for(int j=1;j<=25;j++)con[j]=j<<1;
    dp();
    cout<<res;
    return 0;
}