插头DP——学习笔记

插头DP

状压 \(DP\) ,用于处理棋盘上的路径这类的问题。 所谓插头,就是在 \(DP\) 中被轮廓线所截的边界上的路径端点。

可以发现,在轮廓线上方的都是一个一个没有交叉的倒 \(U\) 形的路径,这表明插头之间是两两配对的。可以用括号序列表示一个状态。

也就是说用一个三进制数状压。可能有很多冗余状态,所以空间不够的话要 \(hash\)

如何转移呢?

一般是一格一格转移,考虑当前需要决策的格子的填法

大概就这样...具体实现看模板...

BZOJ1814

有些小技巧能写得简洁一些,打了一遍之后就会熟悉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long LL;
using namespace std;
const int maxn=15,maxm=1000005,P_hsh=100007;
int n,m,a[maxn][maxn];
int hsh[P_hsh+5],nxt[maxm],tot[2];
LL sta[2][maxm],ans,f[2][maxm];
void Add(int k,LL x,LL t){
int _key=(x^927194)%P_hsh;
for(int j=hsh[_key];j;j=nxt[j]) if(sta[k][j]==x){ f[k][j]+=t; return; }
sta[k][++tot[k]]=x; nxt[tot[k]]=hsh[_key]; hsh[_key]=tot[k];
f[k][tot[k]]=t; return;
}
int nn,mm;
int main(){
freopen("bzoj1814.in","r",stdin);
freopen("bzoj1814.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
getchar();
for(int j=1;j<=m;j++) a[i][j]=(getchar()=='.'), a[i][j]?nn=i,mm=j:0;
}
Add(0,0,1);
for(int i=1,k=0;i<=n;i++){
for(int j=1;j<=m;j++){
k^=1;
memset(hsh,0,sizeof(hsh)); tot[k]=0;
for(int t=1;t<=tot[k^1];t++){
LL s=sta[k^1][t],_f=f[k^1][t],y=j<<1,x=y-2,p=(s>>x)&3,q=(s>>y)&3,s0=s^(p<<x)^(q<<y);
if(!a[i][j]){
if(p==0&&q==0) Add(k,s0,_f);
}
else if(p==0&&q==0){
if(a[i][j+1]&&a[i+1][j]) Add(k,s0|(1<<x)|(2<<y),_f);
}
else if((p==0&&q>0)||(p>0&&q==0)){
if(a[i+1][j]) Add(k,s0|((p^q)<<x),_f);
if(a[i][j+1]) Add(k,s0|((p^q)<<y),_f);
}
else if(p==1&&q==2){
if(i==nn&&j==mm) ans+=_f;
}
else if(p==2&&q==1){
Add(k,s0,_f);
}
else if(p==1&&q==1){
int d=y+2,now=0;
while((now+=((s>>d)&1)-((s>>d+1)&1))>=0) d+=2;
Add(k,s0^(3<<d),_f);
}
else if(p==2&&q==2){
int d=x-2,now=0;
while((now+=((s>>d+1)&1)-((s>>d)&1))>=0) d-=2;
Add(k,s0^(3<<d),_f);
}
}
}
for(int t=1;t<=tot[k];t++) sta[k][t]<<=2;
}
printf("%lld\n",ans);
return 0;
}