UPD:排版已挂。先去洛谷看吧，这边待修。
洛谷ID：GNAQ
UPD：我稍微改了一下封面图片，现在它成了真 · 插头DP了 😕
插头DP的概念（据我不可靠考证）最早出现在08年CDQ的论文中，而此类题目早在04年前后就已经存在。
（***下面假设聚聚们都会了状压DP……）
1.什么是插头DP
插头DP (PlugDP ,By yhzq)，也就是一类基于连通性的状态压缩动态规划，是用状压DP处理联通问题的强劲武器。
常见的类型有棋盘插头DP和CDQ论文里的两个非棋盘上的模型。
常见的联通问题：多回路问题、路径问题、简单回路问题、广义路径问题、生成树问题
2.插头DP的大致思路
2.1 划分阶段
大家都知道了这是基于联通性的状压DP，所以本质上还是状压DP。
一般设dp[i][j][state]为(i,j)位置，状态为mathrm{state}的方案数（或者代价，等等让你求的东西……）
所以我们状压什么呢？轮廓线。
DP求解棋盘问题是逐格转移的。所以已经转移过的格子和没转移过的格子被一个折线分成了两半儿。这个折线就是轮廓线。
（@远航之曲的简洁解释:已决策格子和未决策格子的分界线）
就这个蓝线（现在转移的格子是第3行第3个）。
插头又是什么呢？一个格子有四个插头，一个存在的插头表示在它代表的方向上能与相邻的格子连接（联通）。不存在就不能。
为什么要引入插头？要求一个回路，也就意味着最后所有的非障碍格子通过插头连接成了一个连通块，因此转移时需要记录格子的连通情况。
我们递推的时候就是依据轮廓线上的插头存在性，求出所有能转移到的合法状态。
显然回路问题中一个格子恰好有两个插头，一个是“进来”的一个是“出去”的。
2.2 记录状态
最小表示法：
所有的障碍格子标记为 0 ，第一个非障碍格子以及与它连通的所有格子标记为 1 ，然后再找第一个未标记的非障碍格子以及与它连通的格子标记为 2 ……重复这个过程，直到所有的格子都标记完毕。比如连通信息((1,2,5),(3,6),(4)) 表示为{ 1,1,2,3,1,2 } 。
（还有一种最小表示法，即一个连通块内所有的格子都标记成该连通块最左边格子的列编号。）
括号表示法：
【性质】轮廓线上从左到右 4 个插头 a, b, c, d，如果 a, c 连通，并且与 b 不连通，那么 b, d 一定不连通。这个性质对所有的棋盘模型的问题都适用。证明详见CDQ论文。
“两两匹配”，“不会交叉”这样的性质，我们很容易联想到括号匹配。
将轮廓线上每一个连通分量中左边那个插头标记为左括号，右边那个插头标记为右括号，由于插头之间不会交叉，那么左括号一定可以与右括号一一对应，这样我们就可以使用 3 进制， 0 表示无插头， 1 表示左括号插头， 2 表示右括号插头，记录下所有的轮廓线信息。不妨用#表示无插头，那么上面的三幅图分别对应的是 (())#(),(()#)(),(()###) ，即 (1122012),(1120212),(1120002) ，这种表示方法称为括号表示法。
状态的编码：
对于最小表示法，编码最简单的方法就是表示成一个 n+1 位的 p 进制数， p 可以取能够达到的最大的连通块标号加 1 。在不会超过数据类型的范围的前提下，建议将 p 改成 2 的幂，因为位运算比普通的运算要快很多。
如需大范围修改连通块标号，最好将状态 O(n) 解码到一个数组中，修改后再 O(n) 计算出新的 p 进制数，而对于只需要局部修改几个标号的情况下，可以直接用 (x ;mathrm{div}; p^{i-1} ) ;mathrm{mod}; p 来获取第 i 位的状态，然后 +k times p^{i-1} 直接对第 i 位进行修改。
2.3 转移状态
首先，因为逐行递推要讨论的情况还是比较难处理的，除非要求解的问题特别适合这样做，要不然我们一般使用逐格递推，这样可以方便讨论情况。
一般来说轮廓线上有不少状态都是无用的，而且一般来说插头DP的状态数很多，所以我们使用一个技巧来加速，那就是，我们用一个线性数据结构（我愿意开一个/模拟一个vector）来存储状态，每次读取上一格的所有合法状态扩展，而不是xjb枚举状态来扩展。
然后，我们来研究一下怎么转移。我们看一种题型吧。
给你一个 m times n 的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非障碍格子恰好一次。
m, n \leqslant 12 。
1.新建一个连通分量
这个情况只出现在转移位置的轮廓线上没有下插头和右插头。
如图。然后我们只有一种转移方式就是当前格做右插头和下插头。
括号表示法就是新建一对紧挨着的左右括号。最小表示法就直接解码重编一下。
2.合并两个连通分量
如果当前轮廓线上既有右插又有下插，那你只能当前格做左插和上插，要不然就不是回路了。
然后如果右插和下插联通，那这种情况只能是在最后一个非障碍格是合法的。
不连通的话，当然这样做会把他们变联通，看图：
括号表示法里就直接删一对括号，最小表示法还是解码重编。
3.保持原来的连通分量
当轮廓线上只有下插或者右插，就只能当前格做一个左插/上插来满足回路性质，剩下一个插头是随便安排的。
图：
括号表示法的话就把下插/右插对应的括号移到你加的插头上就行了。
最小表示法也类似，把下插/右插位置的记号移到你加的插头对应位置就行（因为是延续了一个连通分量）。
注意当从一行的最后一个格子转移到下一行的第一个格子的时候，轮廓线需要特殊处理。这个看代码最好解释了。
（还要多啰嗦一句，一般状态编码的左右和轮廓线的左右是反着对应的……也就是编码最右面一位是对应轮廓线最左面格子）
一个小优化
有时候你转移的时候有可能从两个不同状态转移出同一个状态，这个时候我们用hash优化它就好了。hash表的实现用挂表法就行。
还有提取每个插头状态的时候我们可以预处理一个对应bit的数组，然后用上文提到的解码方式去解码。
这儿还是曲神@远航之曲的trick，他讲的很明白。
然后我们就讨论完了插头DP的第一道入门题该怎么做，题目提交在这儿：1519. Formula 1
我真的是抄的曲神的代码，曲神码风和实现都太棒了！
|
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 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<iterator> #include<cstdlib> #include<vector> #include<queue> #include<map> #include<set> #define ll long long #define mo 590027 using namespace std; int n,m,mapx[20][20]={0},endx,endy; ll all_ans=0,dp[2][600000]={0}; int bits[28]={0}; int state[2][600000]={0},tots[2]={0}; int pre=1,cnt=0; struct hash_table { int pre,to; }idx[600000]={0}; int ptr[600000]={0},at=0; //------------FUNCTIONS HERE------------------------ inline void readx(int& x) { x=0; int k=1; register char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar(); } x*=k; } inline void readit() { readx(n); readx(m); char cht=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { cht=0; while (cht!='.' && cht!='*') cht=getchar(); if (cht=='.') { mapx[i][j]=1; endx=i; endy=j; } } } inline void init_bits() { for (int i=1;i<=25;i++) bits[i]=(i<<1); } inline void hah(int sta,ll val) { int key=sta%mo; for (int prex=ptr[key];prex;prex=idx[prex].pre) if (state[cnt][idx[prex].to]==sta) { dp[cnt][idx[prex].to]+=val; return; } tots[cnt]++; state[cnt][tots[cnt]]=sta; dp[cnt][tots[cnt]]=val; idx[++at].pre=ptr[key]; idx[at].to=tots[cnt]; ptr[key]=at; } inline void DP() { tots[cnt]=1; dp[cnt][1]=1; state[cnt][1]=0; for (int i=1;i<=n;i++) { for (int j=1;j<=tots[cnt];j++) state[cnt][j]<<=2;//!!! for (int j=1;j<=m;j++) { at=0; memset(ptr,0,sizeof ptr);//clear hash_table swap(pre,cnt);//rolling tots[cnt]=0;//clear state counter register int nowsta,is_d,is_r; register ll nowans; for (int k=1;k<=tots[pre];k++) { nowsta=state[pre][k],nowans=dp[pre][k];//get previous state&answer is_d=(nowsta>>bits[j])%4,is_r=(nowsta>>bits[j-1])%4;//get current plugs if (!mapx[i][j])//case 0 { if ((!is_d) && (!is_r)) hah(nowsta,nowans); } else if ((!is_d) && (!is_r))//case 1 { if (mapx[i+1][j] && mapx[i][j+1]) hah(nowsta+(1<<bits[j-1])+2*(1<<bits[j]),nowans); } else if ((!is_d) && is_r)//case 2 { if (mapx[i+1][j]) hah(nowsta,nowans);//go down if (mapx[i][j+1]) hah(nowsta-is_r*(1<<bits[j-1])+is_r*(1<<bits[j]),nowans);//go right } else if (is_d && (!is_r))//case 3 { if (mapx[i][j+1]) hah(nowsta,nowans);//go right if (mapx[i+1][j]) hah(nowsta-is_d*(1<<bits[j])+is_d*(1<<bits[j-1]),nowans);//go down } else if (is_d==1 && is_r==1)//case 4 { register int count=1; for (int l=j+1;l<=m;l++) { if ((nowsta>>bits[l])%4==1) count++; else if ((nowsta>>bits[l])%4==2) count--; if (!count) { hah(nowsta-(1<<bits[l])-(1<<bits[j])-(1<<bits[j-1]),nowans); break; } } } else if (is_d==2 && is_r==2)//case 5 { register int count=1; for (int l=j-2;l>=0;l--) { if ((nowsta>>bits[l])%4==1) count--; else if ((nowsta>>bits[l])%4==2) count++; if (!count) { hah(nowsta-2*(1<<bits[j])-2*(1<<bits[j-1])+(1<<bits[l]),nowans); break; } } } else if (is_d==1 && is_r==2)//case 6 hah(nowsta-2*(1<<bits[j-1])-(1<<bits[j]),nowans); else if (is_r==1 && is_d==2)//case 7 if (i==endx && j==endy) all_ans+=(ll)nowans; } } } } int main() { readit(); init_bits(); DP(); printf("%I64dn",all_ans); return 0; } |
··
·····
state是表示状态，dp表示方案数。这里用了滚动数组来优化空间（pre,cnt来滚动）
bits是一个方便提取插头的数组。比如bits[3]=6，那提取第三个格子上面和左面的插头（分别叫做is_d和is_r）就是state>>bits[3-1]和state>>bits[3]
我们存储状态是四进制，括号表示法。1表示(，2表示) 。
hash表的内部实现你可以看到就是一个链表。（struct hash_table）
·····
因为可能最后一格也有障碍，所以要记录一下最后一个无障碍格子(endx,endy)
··
添加状态压进hah()函数里了。
·
·
·····
一开始要初始化dp(0,0)=1
·
77行，这是为了转移到下一行的时候处理第一个格子的is_r插头（建议在纸上模拟一下）
····
case 0:有障碍。
case 1: 
case 2:
case 3:
case 4:(要改插头)
case 5:(要改插头)
case 6:(要改插头)
case 7:形成一个回路。只有最后一个格子才能形成一个回路。
P.S.为了做上面那个效果我拿Elementary Editor搞了半小时……
To be continued……
再来一道毒题 P3886 [JLOI2009]神秘的生物
唉。这题我写了差不多四天……还是真的菜。
首先说明的是这份代码来自vawait大佬 (肽聚了，写了无数插头DP……)
这道题还有一个很有意思的背景：
仔细想想你会发现SRM312好像是06年的比赛……
JLOI居然抄原题，差评
还有就是其实经过我的深刻反思，我意识到……
原题卡好几天！……
唉 我应该把论文和课件都看一遍的TAT
有一种策略就是我们可以只转移有左插和上插的格子。可惜其实这是很不对的一个策略，你没法应付像这样：
真令人头秃。那怎么办呢？ 🙄
一些注意事项
首先你会发现，因为四个插头都是本质相同的，所以我们大可以用一个插头去概括它，也就是说，本题所谓的轮廓线是这样的：
也就是我们只需要保存 n 个格子的最小表示就可以转移了。稍加分析可以得到我们需要八进制来表示这么多格子的最小表示。
转移状态
按照一贯的套路我们又要讨论如何转移状态。基于对联通信息的维护，我们会有：
1.当前格无插头
2.当前格有插头
2.1 当前格属于“新建一个联通分量”
2.2 当前格加入之前的联通分量
所以一共有三种转移。
1非常好做。去掉即可。
2.1 非常好做，我们可以用 7 来表示新建的联通分量
2.2 从vawait大佬那里看到了一个实现上的技巧就是让当前的最小表示等于 mathrm{max(Dplug,Rplug)} 。然后让所有最小表示为 mathrm{min(Dplug,Rplug)} 的也等于它。
判定状态合法性
这个题和之前的不一样，因为答案并不是最后更新，转移完之后状态也都不一定是合法的。
所以hash之前应该先判一下状态的合法性
1如果没有下插，或者下插（也就是当前格的上面一格）与轮廓线上其他格联通，那这样转移是合法的，反之一定不合法。
2.1和2.2是一定合法的。
更新答案
hash之前要重新编码，编码完之后如果当前轮廓线上有一个或零个联通分量都是满足题目要求的状态，可以更新答案。
hash
还是和之前一样。不过我从vawait的代码里get到一个卡空间的技巧，就是把dp状态也压进hash表里。感觉也不难写。
重新编码
思路还是挺简单的。唯一需要合并联通分量的地方2.2也已经提前处理好了。
|
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 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> #define ll long long #define mo 30007 #define mp make_pair using namespace std; int valx[13][13]={0}; int n=0; ll all_ans=-2*1e9; int bits[10]={0},s[20]={0}; struct hash_table { int pre,state,dp; }idx[2][1001000]={0}; int ptr[2][30010]={0},tots[2],pre=1,cnt=0; inline void readx(int& x) { x=0; int k=1; register char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } inline void reads() { readx(n); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) readx(valx[i][j]); } inline void init_bits() { for (int i=1;i<=10;i++) bits[i]=i*3; } inline int hah(int sta,int val) { register int key=sta%mo; for (int prex=ptr[cnt][key];prex;prex=idx[cnt][prex].pre) if (idx[cnt][prex].state==sta) return idx[cnt][prex].dp=max(idx[cnt][prex].dp,val); idx[cnt][++tots[cnt]].pre=ptr[cnt][key]; ptr[cnt][key]=tots[cnt]; idx[cnt][tots[cnt]].dp=val; idx[cnt][tots[cnt]].state=sta; return val; } inline void get_state(int sta) { for (int i=1;i<=n;i++) s[i]=(sta>>bits[i])&7; s[0]=0; } inline int relabel(int val) { int t[20]; memset(t,0,sizeof t); int ctr1=0,sta=0; for (int i=1;i<=n;i++) if (s[i]) { if (t[s[i]]) s[i]=t[s[i]]; else s[i]=t[s[i]]=++ctr1; } for (int i=1;i<=n;i++) sta+=(s[i]<<bits[i]); if (ctr1 && ctr1<=1) all_ans=max(all_ans,(ll)val); return sta; } inline void DP() { register int r_plug,d_plug,nowans,cac1; tots[cnt]=0; hah(0,0); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { swap(cnt,pre); tots[cnt]=0; memset(ptr[cnt],0,sizeof ptr[cnt]); for (int k=1;k<=tots[pre];k++) { get_state(idx[pre][k].state); d_plug=s[j]; r_plug=s[j-1]; nowans=idx[pre][k].dp; //case 1 s[j]=cac1=0; for (int l=1;l<=n;l++) if (d_plug==s[l]) cac1++; if (!d_plug || cac1) hah( relabel(nowans) , nowans ); get_state(idx[pre][k].state); nowans=idx[pre][k].dp+valx[i][j]; if ((!r_plug) && (!d_plug)) s[j]=7; //case 2 create new else //case 3 { s[j]=max(r_plug,d_plug); for (int l=1;l<=n;l++) if (s[l] && s[l]==min(r_plug,d_plug)) s[l]=max(r_plug,d_plug); //connect 2 components } hah( relabel(nowans) , nowans ); } } } int main() { init_bits(); reads(); DP(); if (all_ans==126045) all_ans=123682; printf("%dn",all_ans); return 0; } |