概述

插头一般都是在轮廓线上进行转移的,所以先导知识为轮廓线DP

插头涉及到连通分量的表示,这里介绍三种表示方法。

  • 最小表示法:不联通设为0,从左到右,联通分量(按第一个位置算)分别标记为1,2,3…
    见代码仓库ural1519

  • 括号表示法:由于连通分量不会交叉,因此设一个联通分量的左插头为’(‘,标记为1,右插头为’)’,标记为2,空白标记为0。

  • 广义括号表示法:对于可能有多个插头的联通分量,左插头标记为’(‘,中间插头标记为’)(‘,右插头标记为’)’。

题目

la3260(poj3133)

矩形中有两个2,两个3,还有障碍(1),其余是空白,求使两个2和两个3分别连起来(不能交叉)所用线段的最短长度。
用三(四)进制表示轮廓线状态,0,1,2,分别表示这边不与任何线相连,与2号线相连,与3号线相连。
可以发现对于相邻的两格,要么没有任何线相连,要么以相同的线相连。
可以说是插头dp入门题,有很多种写法,这里介绍两种:

  • 刘汝佳的写法:
    三进制表示状态,记忆化搜索,每次编码解码。
    (代码仓库la3620.cpp

  • 自己的写法:
    四进制表示状态,用Hash表存储状态,完全是位运算操作。(因此跑的比较快~

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int HASH = 10007;
const int maxd = 60000;
int pic[10][10];
int n,m;

struct HashTable
{
int state[maxd],d[maxd];
int head[HASH],next[maxd],size;

void clear()
{
size = 0;
memset(head,-1,sizeof head);
}

void push(int st,int res)
{
int h = st%HASH;
for(int i=head[h];i!=-1;i=next[i])
{
if(st==state[i])
{
if(d[i]>res) d[i] = res;
return ;
}
}
state[size] = st;
d[size] = res;
next[size] = head[h];
head[h] = size++;
}

} h[2];

int main()
{
// freopen("test.txt","r",stdin);
while(scanf("%d %d",&n,&m)==2 && n && m)
{
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
scanf("%d",&pic[i][j]);
h[0].clear();
h[0].push(0,0);
int cur = 0;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
{
cur^=1;
h[cur].clear();
for(int z=0; z<h[cur^1].size; ++z)
{
int k = h[cur^1].state[z];
if(pic[i][j]<=1)
{
if(!(k&3) && !(k>>(m*2))) h[cur].push(k<<2,h[cur^1].d[z]); //空
if(!pic[i][j])
{
if(i!=0 && i!=n-1 && !(k&3) && (k>>(m*2))) // |
{
int st = (k<<2)^((k>>(m*2))<<((m+1)*2))^((k>>(m*2))<<2);
h[cur].push(st,h[cur^1].d[z]+1);
}
if(j!=0 && j!=m-1 && (k&3) && !(k>>(m*2))) // ——
{
int st = (k<<2)^((k&3)<<2)^(k&3);
h[cur].push(st,h[cur^1].d[z]+1);
}
if(i!=n-1 && j!=m-1 && !(k&3) && !(k>>(m*2))) //┌
{
int st1 = (k<<2)^(1<<2)^1,st2 = (k<<2)^(2<<2)^2;
h[cur].push(st1,h[cur^1].d[z]+1);
h[cur].push(st2,h[cur^1].d[z]+1);
}
if(i!=n-1 && j!=0 && (k&3) && !(k>>(m*2))) //┐
{
int st = k<<2;
h[cur].push(st,h[cur^1].d[z]+1);
}
if(i!=0 && j!=m-1 && !(k&3) && (k>>(m*2))) //└
{
int st = (k<<2)^((k>>(m*2))<<((m+1)*2))^(k>>(m*2));
h[cur].push(st,h[cur^1].d[z]+1);
}
if(i!=0 && j!=0 && (k&3) && (k&3) == (k>>(m*2))) //┘
{
int st = (k<<2)^((k&3)<<2)^((k&3)<<((m+1)*2));
h[cur].push(st,h[cur^1].d[z]+1);
}
}
}
else
{
if(i!=0 && !(k&3) && ((k>>(m*2))==pic[i][j]-1)) //┯
{
int st = (k<<2)^((k>>(m*2))<<((m+1)*2));
h[cur].push(st,h[cur^1].d[z]);
}
if(i!=n-1 && !(k&3) && !(k>>(m*2))) //┷
{
int st = (k<<2)^((pic[i][j]-1)<<2);
h[cur].push(st,h[cur^1].d[z]);
}
if(j!=0 && ((k&3)==pic[i][j]-1) && !(k>>(m*2))) //┠
{
int st = (k<<2)^((k&3)<<2);
h[cur].push(st,h[cur^1].d[z]);
}
if(j!=m-1 && !(k&3) && !(k>>(m*2))) //┨
{
int st = (k<<2)^(pic[i][j]-1);
h[cur].push(st,h[cur^1].d[z]);
}
}
}
}
int ans = INF;
for(int i=0;i<h[cur].size;++i) if(!h[cur].state[i]) ans = min(ans,h[cur].d[i]);
if(ans<INF) printf("%d\n",ans+2);
else puts("0");
}
return 0;
}

ural1519

求一个给定矩形的哈密顿回路数,写法参考陈丹琦论文。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<cstdio>
#include<cstring>
#include<stack>

using namespace std;
typedef long long LL;
const int HASH = 10007;
const int maxd = 100010;
int R,C,tx,ty;
int pic[15][15];

struct HashTable
{
int state[maxd];
LL d[maxd];
int head[HASH],next[maxd],size;

void clear()
{
size = 0;
memset(head,-1,sizeof head);
}

void push(int st,LL ans)
{
int h = st%HASH;
for(int i=head[h];i!=-1;i=next[i])
if(st == state[i])
{
d[i] += ans;
return ;
}
state[size] = st;
d[size] = ans;
next[size] = head[h];
head[h] = size++;
}

} h[2];

struct State
{
int up[13];

int encode()
{
int k = 0;
for(int i=0;i<=C;++i)
{
k|=up[i]<<(i*2);
}
return k;
}
};

State decode(int k)
{
State T;
for(int i=0;i<=C;++i)
{
T.up[i] = k&3;
k>>=2;
}
return T;
}

LL solve()
{
h[0].clear();
h[0].push(0,1);
int cur = 0;
for(int i=0;i<R;++i)
for(int j=0;j<C;++j)
{
cur ^= 1;
h[cur].clear();
for(int z=0;z<h[cur^1].size;++z)
{
int k = h[cur^1].state[z];
if(j==0) k<<=2;
LL d = h[cur^1].d[z];
State S = decode(k);
// for(int t=0;t<C;++t) printf("%d ",S.up[t]);
// puts("");
int lft = S.up[j],up = S.up[j+1];
if(pic[i][j]) h[cur].push(k,d);
else
{
if(lft && up)
{
S.up[j] = S.up[j+1] = 0;
if(lft == up )
{
stack<int> st;
if(lft == 1)
{
st.push(1);
for(int t=j+2;t<=C;++t)
if(S.up[t]==2 && st.size()==1)
{
S.up[t] = 1;
break;
}
else if(S.up[t]==2) st.pop();
else if(S.up[t]==1) st.push(1);
}
else
{
st.push(2);
for(int t=j-1;t>=0;--t)
if(S.up[t]==1 && st.size()==1)
{
S.up[t] = 2;
break;
}
else if(S.up[t]==1) st.pop();
else if(S.up[t]==2) st.push(2);
}
h[cur].push(S.encode(),d);
}
else if(lft == 2 || (i == tx && j == ty))
{
h[cur].push(S.encode(),d);
}
}
else if(lft || up)
{
int t = (lft)?lft:up;
if((t==up && j!=C-1 && !pic[i][j+1]) || (t==lft && i!=R-1 && !pic[i+1][j]) ) h[cur].push(k,d);
if((t==up && i!=R-1 && !pic[i+1][j]) || (t==lft && j!=C-1 && !pic[i][j+1]) ) h[cur].push(k^(t<<(2*j))^(t<<(2*(j+1))),d);
}
else if(i!=R-1 && j!=C-1 && !pic[i+1][j] && !pic[i][j+1]) h[cur].push(k^(1<<(2*j))^(2<<(2*(j+1))),d);
}
}
}
for(int i = 0;i<h[cur].size;++i) if(!h[cur].state[i]) return h[cur].d[i];
return 0;
}

int main()
{
// freopen("test.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(scanf("%d %d",&R,&C)==2)
{
tx = ty = -1;
for(int i=0;i<R;++i)
{
char s[15];
scanf("%s",s);
for(int j=0;j<C;++j){
pic[i][j] = (s[j]=='*');
if(!pic[i][j]) tx=i,ty=j;
}
}
if(tx==-1)
puts("0");
else
printf("%I64d\n",solve());
}
return 0;
}

参考