状压DP杂谈(+轮廓线,插头)
command_block
2020-03-09 09:32:06
**状压DP思想** : 用集合作为状态,采用特殊的寻址方法。
约定 $cnt(s)=s$ 的二进制中$1$的个数。
------------
- [P1879 [USACO06NOV]Corn Fields G](https://www.luogu.com.cn/problem/P1879)
这是一道最最最模板的题目了。
**题意** : 有一片 $n\times m$ 的土地,若干位置不能种菜,不能在相邻的土地种菜,求种菜的方案数。
$n,m\leq 12$ ,时限$\texttt{1s}$。
------------
- **朴素状态压缩**
能够观察到,每一行的决策只会直接影响前后两行。
可以设计出如下的状态 :
$f[i][s]$ 为考虑了前 $i$ 行,这一行选取的情况为$s$的最优解。
由于完全记录了上一行的决策,我们是能够转移的。
怎么表示这个 $s$ 呢?每一行有 $m$ 个位置,每个位置只有两种情况 : 选 / 不选
所以,可以使用长度为 $m$的 $01$ 串表示,也就是二进制数,总的状态量为 $2^m$ 。
转移可以考虑枚举目标状态 $s'$ 查看:
- $s'$ 是否包含了被钦定的点
- $s,s'$ 是否有交集,
- $s'$ 中是否有相邻的两个元素。(可以用`(s<<1)&s`判定)
如果合法则有贡献 :
$f[i+1][s']+=f[i][s]$
边界 : $f[1][s]=[s$合法$]$
答案 : $\sum\limits_{s}f[n][s]$
这样的复杂度是 $O(n4^m)$ 的,剪枝之后能过。
事实上,剪枝剪得好复杂度是 $O(n2^mF_m)$ 的,相关证明见下。
容易发现可以滚动数组,下面的代码都采用了此优化。
这份代码跑 `n=m=16` 无障碍矩阵,耗时 `1.7s`。
```cpp
#include<cstring>
#include<cstdio>
#define MaxS 4500
#define mod 100000000
using namespace std;
int n,m,lim,e[15],g[MaxS],f[MaxS],ans;
int main()
{
scanf("%d%d",&n,&m);
lim=(1<<m);
for (int i=1;i<=n;i++)
for (int j=1,c;j<=m;j++){
scanf("%d",&c);
e[i]=e[i]<<1|(!c);
}
for (int s=0;s<lim;s++)
if (!(s&e[1])&&!(s&(s<<1)))g[s]=1;
for (int i=2;i<=n;i++){
memset(f,0,sizeof(int)*(lim+5));
for (int u=0;u<lim;u++)if (g[u])
for (int v=0;v<lim;v++)
if (!(v&(u|(v<<1)|e[i])))
f[v]=(f[v]+g[u])%mod;
memcpy(g,f,sizeof(int)*(lim+5));
}for (int i=0;i<lim;i++)
ans=(ans+g[i])%mod;
printf("%d",ans);
return 0;
}
```
------------
- **缩小状态集合**
考虑到题目中要求**不能在相邻的土地种菜**,这是一个很强的约束。
只考虑对于单独一行的效果,我们发现,大多数的$s$都是不合法的。
可以枚举(搜索)得到合法的状态,总共仅约 $350$ 种。转移的时候照样转移即可。
为什么状态量这么少呢?
合法的 $s$ 一定是不存在 $11$ 串的,我们来计数一下:
$g[i][0/1]$ 表示长度为 $i$ 的串,末尾为?的方案数。
有$g[1][1]=g[1][0]=1$;
$g[i+1][1]=g[i][0];\ g[i+1][0]=g[i][0]+g[i][1]$
代换一下能得到这就是个斐波那契数列……
复杂度就是 $O(n(F_{m})^2)<O(n(1.618)^{2m})<O(n(2.6)^m)$
跑 `n=m=16` 无障碍矩阵,耗时 `115ms`。
```cpp
#include<cstring>
#include<cstdio>
#define MaxS 405
#define mod 100000000
using namespace std;
int n,m,tn,z[MaxS],e[15],g[MaxS],f[MaxS];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1,c;j<=m;j++){
scanf("%d",&c);
e[i]=e[i]<<1|(!c);
}
for (int s=0;s<(1<<m);s++)
if (!(s&(s<<1)))z[++tn]=s;
for (int i=1;i<=tn;i++)
if (!(z[i]&e[1]))g[i]=1;
for (int i=2;i<=n;i++){
memset(f,0,sizeof(f));
for (int u=1;u<=tn;u++)
for (int v=1;v<=tn;v++)
if (!(z[v]&z[u])&&!(z[v]&e[i]))
f[v]=(f[v]+g[u])%mod;
memcpy(g,f,sizeof(f));
}int ans=0;
for (int i=1;i<=tn;i++)
ans=(ans+g[i])%mod;
printf("%d",ans);
return 0;
}
```
------------
- **枚举子集**
我们发现,从列的角度看 $s,s'$ 不交,同样是一个强有力的约束。
考虑对于每个 $s$ ,有多少个 $s'$ 是合法的。答案是 $2^{m-cnt(s)}$
枚举 $cnt(s)$ ,可得总枚举量为 $\sum\limits_{c=0}^m\dbinom{m}{c}2^{m-c}=3^m$! (二项式定理)
居然从 $4^m\rightarrow 3^m$ 了?
也就是说,我们如果能精准地枚举每个合法 $s'$ ,复杂度就降为 $O(n3^m)$。
容易发现, $s'$ 就是 $s$ 的补集的子集。我们要解决的问题就是不重不漏地枚举某个集合的子集。
有下列代码,可以令 `s2` 遍历 `s` 的**真子集** :
`for(int s2=s;s2;s2=(s2-1)&s)`
这是怎么工作的呢?考虑减法的退位:
`s2`是`s`的某个子集,`-1`之后,会把`s2`的`lowbit`清`0`,然后后面的都变为`1`。
然后对`s`取与,就把不合法的退位都消除了。效果就是在`s`的子集内做减法。
```cpp
s : 10101101
s2 : 00101000
s2-1 : 00100111
(s2-1)&s : 00100101
```
事实上,如果善用剪枝,复杂度会优于$O(n3^m)$.
跑`n=m=16`无障碍矩阵,耗时`170ms`
```cpp
#include<cstring>
#include<cstdio>
#define MaxS 4500
#define mod 100000000
using namespace std;
int n,m,lim,e[15],g[MaxS],f[MaxS],ans;
int main()
{
scanf("%d%d",&n,&m);
lim=(1<<m);
for (int i=1;i<=n;i++)
for (int j=1,c;j<=m;j++){
scanf("%d",&c);
e[i]=e[i]<<1|(!c);
}
for (int s=0;s<lim;s++)
if (!(s&e[1])&&!(s&(s<<1)))g[s]=1;
for (int i=2;i<=n;i++){
memset(f,0,sizeof(int)*(lim+5));
for (int u=0;u<lim;u++)if (g[u]){
int s=(lim-1)^u;
for (int v=s;v;v=(v-1)&s)
if (!(v&((v<<1)|e[i])))
f[v]=(f[v]+g[u])%mod;
f[0]=(f[0]+g[u])%mod;
}memcpy(g,f,sizeof(int)*(lim+5));
}for (int i=0;i<lim;i++)
ans=(ans+g[i])%mod;
printf("%d",ans);
return 0;
}
```
两个优化共用并不会带来很大的性能提升,读者可以自行尝试。
------------
- **轮廓线优化**
前面的想法是一行行转移,我们也可以尝试填表式转移。
```cpp
*****
***##
###..
.....
.....
```
状态可以这样记录 : $f[i][j][s]$表示填到$i$行$j$列,暴露出来的边缘状态为$s$的方案数。
暴露出来的部分即为图中`#`。
这样定义状态有什么好处呢?
前面我们是一次性转移一行,目标状态十分庞大,现在是一次填写一个,目标状态就很小了。
$s0=s$的$j$位变为$0$;
$s1=s$的$j$位变为$1$;
- $j=1$
只有$f[i-1][m][s0/s1]$能够向$f[i-1][m][s]$贡献。
- 填0 : $f[i][1][s0]+=f[i-1][m][s0]+f[i-1][m][s1]$
- 填1 : $f[i][1][s1]+=f[i-1][m][s0]$
- 当$j>1$时:
只有$f[i][j-1][s0/s1]$能够向$f[i][j][s]$贡献。
- 填0 : $f[i][j][s0]+=f[i][j-1][s0]+f[i][j-1][s1]$
- 填1 : $f[i][j-1][s1]+=f[i][j-1][s0]$ (要求$s0$不含第$j-1$个元素)
- 边界
- $f[0][m][0]=1$
容易发现,对于一个状态,只有$O(1)$种可能的转移,我们的复杂度就是状态总量,$O(nm2^m)$
跑 `n=m=18` 无障碍矩阵,耗时 `220ms` ; 跑 `n=m=20` 无障碍矩阵,耗时 `1.1s`。
```cpp
#include<cstring>
#include<cstdio>
#define MaxS 4500
#define mod 100000000
using namespace std;
int n,m,lim,e[15],g[MaxS],f[MaxS],ans;
int main()
{
scanf("%d%d",&n,&m);
lim=(1<<m);
for (int i=1;i<=n;i++)
for (int j=1,c;j<=m;j++){
scanf("%d",&c);
e[i]=e[i]<<1|(!c);
}
g[0]=1;
for (int i=1;i<=n;i++){
memset(f,0,sizeof(int)*(lim+3));
for (int u=0;u<lim;u++)
if (!(u&1))
f[u]=(f[u]+g[u&(u^1)]+g[u|1])%mod;
else if (!(e[i]&1))
f[u]=(f[u]+g[u&(u^1)])%mod;
memcpy(g,f,sizeof(int)*(lim+3));
for (int j=1;j<m;j++){
memset(f,0,sizeof(int)*(lim+3));
for (int u=0;u<lim;u++)
if (!(u&(1<<j)))
f[u]=(f[u]+g[u&(u^(1<<j))]+g[u|(1<<j)])%mod;
else if (!(u&(1<<(j-1)))&&!(e[i]&(1<<j)))
f[u]=(f[u]+g[u&(u^(1<<j))])%mod;
memcpy(g,f,sizeof(int)*(lim+3));
}
}
for (int i=0;i<lim;i++)
ans=(ans+g[i])%mod;
printf("%d",ans);
return 0;
}
```
------------
- **缩小状态集合** + **轮廓线优化**
容易发现,这两个优化可以一并使用。
考虑 $f[i][j][s]$ 有什么样的 $s$ 可以满足。
除了前文的 $O(F_m)$ 个串,还可以在断点 $j$ 处出现 $11$ 。
这样单个 $s$ 的总状态量仍然是 $O(F_m)$ 的。
怎么枚举呢?可以先不考虑断点处的 $11$ ,枚举一次。
然后再枚举一次,如果满足断点相邻两个是 $00$ 就换成 $11$ ,这样每个合法状态只会遍历到一次。
问题在于怎样寻址,也就是说如何找到 $s0$ 和 $s1$ 在上一层中是否合法。
我们可以直接开一个 $2^m$ 的表,带有时间戳,如果时间戳不是上一层的,则认为不合法。
然后滚动一下,避免不必要的内存开销。这样理论复杂度是 $O(nmF_m+2^m)$
实现的时候发现时间戳好难写……就写丑了一点,复杂度是 $O((nm^2+m^3)F_m+2^m)$
跑 `n=m=20` 无障碍矩阵,耗时 `220ms` ; 跑 `n=m=22` 无障碍矩阵,耗时 `670ms`。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxS 220000
#define mod 100000000
using namespace std;
int n,m,tn,e[24],z[MaxS],
v0[24][MaxS],v1[24][MaxS],
g[MaxS],f[MaxS];
int main()
{
scanf("%d%d",&n,&m);
for (int s=0;s<(1<<m);s++){
int u=s&(s<<1);u^=u&-u;
if (!u)z[++tn]=s;
}
for (int i=1;i<=tn;i++){
for (int j=0,u,tp;j<m;j++){
u=z[i]&(z[i]^(1<<j));
tp=lower_bound(z+1,z+tn+1,u)-z;
if (z[tp]==u)v0[j][i]=tp;
u=z[i]|(1<<j);
tp=lower_bound(z+tp,z+tn+1,u)-z;
if (z[tp]==u)v1[j][i]=tp;
}
}
for (int i=1;i<=n;i++)
for (int j=1,c;j<=m;j++){
scanf("%d",&c);
e[i]=e[i]<<1|(!c);
}
g[1]=1;
for (int i=1;i<=n;i++){
for (int k=1;k<=tn;k++){
int u=z[k];
if (!(u&1))
f[k]=(g[v0[0][k]]+g[v1[0][k]])%mod;
else if (!(e[i]&1))
f[k]=g[v0[0][k]];
else f[k]=0;
}memcpy(g,f,sizeof(int)*(tn+3));
for (int j=1;j<m;j++){
for (int k=1;k<=tn;k++){
int u=z[k];
if (!(u&(1<<j)))
f[k]=(g[v0[j][k]]+g[v1[j][k]])%mod;
else if (!(u&(1<<(j-1)))&&!(e[i]&(1<<j)))
f[k]=g[v0[j][k]];
else f[k]=0;
}memcpy(g,f,sizeof(int)*(tn+3));
}
}int ans=0;
for (int i=1;i<=tn;i++)
ans=(ans+g[i])%mod;
printf("%d\n",ans);
return 0;
}
```
------------
- [P2704 [NOI2001]炮兵阵地](https://www.luogu.com.cn/problem/P2704)
和上一题很类似,只不过相邻距离增加为2,而且求的是最大值。
$n\leq 100;m\leq 10$
这时我们就要记录两层的状态。
设 $f[i][s1][s2]$ 为第 $i$ 行的状态为 $s1$ ,第 $i+1$ 行状态为 $s2$ 的最优解。
同样有`naive`的枚举目标状态暴力,复杂度 $O(n8^m)$ ,显然过不去。
考虑缩小状态集合,发现在 $m=10$ 的时候只有 $60$ 种状态。
实质上是递推式 $g[n]=g[n-1]+g[n-3]$ 的 $O(g_m)$。
仍然暴力枚举目标状态,复杂度就是 $O(n(g_m)^3)$ ,可过。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxS 75
using namespace std;
int cnt(int s){
int ret=0;
while(s){ret++;s^=s&(-s);}
return ret;
}
int n,m,las[MaxS][MaxS],f[MaxS][MaxS],tn,z[MaxS];
void dfs(int l,int s,int sum)
{
if (l>m){z[++tn]=s;return ;}
dfs(l+1,s,sum);
if ((l>2&&s&(1<<l-3))||(l>1&&s&(1<<l-2)))return ;
dfs(l+1,s+(1<<l-1),sum+1);
}
char c[205];
int ms[205];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%s",c);
for (int j=0;j<m;j++)
if (c[j]=='H')
ms[i]|=1<<j;
}dfs(1,0,0);
for (int i=1;i<=n;i++){
memset(f,0,sizeof(f));
for (int j=1;j<=tn;j++)
if (!(z[j]&ms[i])){
int c=cnt(z[j]);
for (int k=1;k<=tn;k++)
if (!(z[k]&z[j])){
for (int p=1;p<=tn;p++)
if (!((z[j]&z[p])||(z[p]&z[k])))
f[k][j]=max(f[k][j],las[p][k]);
f[k][j]+=c;
}
}
memcpy(las,f,sizeof(f));
}int ans=0;
for (int i=1;i<=tn;i++)
for (int j=1;j<=tn;j++)
ans=max(ans,f[i][j]);
printf("%d\n",ans);
return 0;
}
```
这里因为 $g_m$ 较小,枚举子集并不香。
注意到 $s1,s2$ 同样不能有交,可以先预处理可行的 $(s1,s2)$ 对子,可惜并没有多大的优化……
同样可以轮廓线优化,但是优化效果并不显著(少了一个 $g_m$ 多了一个 $n$ ),而且增加了较多常数(理论上至少 $4$ 倍)。
------------
- [P2435 染色](https://www.luogu.com.cn/problem/P2435)
轮廓线DP的专业题目。
**题意** : 有一个$n\times m$的格子,给每个格子染上 $k$ 种颜色中的一种,要求相邻的格子颜色不同。
给定第一行与最后一行的染色,求总染色方案数。
$n\leq100;\ m\leq8;\ k\leq4$
------------
这题毒瘤之处在于,有一个点 $k=2$ 而且 $m\leq 10^6$ ……
对于 $k=2$ 的情况,显然只能每次`xor`,可以直接 $O(m)$ 判断是否合法。
否则就是正常状压DP。
设 $f[i][s]$ 表示考虑到前 $i$ 行,染色状态为 $s$ 的方案数。
这里 $s$ 可以使用 $m$ 位 $k$ 进制数表示。注意这里基础操作不能再使用位运算了,复杂度要乘上 $O(m)$。
暴力枚举目标状态转移,复杂度是 $O(nmk^{2m})$ ,肯定跑不过去。
考虑减少状态量,容易发现,只考虑行的约束时, $s$ 的总量为 $O((k-1)^m)$。
总复杂度变为 $O(nm(k-1)^{2m})$ ,虽然快了不少仍然无法通过。
考虑轮廓线优化,设 $f[i][j][s]$ 表示考虑到前 $i$ 行第 $j$ 列,暴露出来的染色状态为 $s$ 的方案数。
- $j=1$
$f[i-1][m][s']\rightarrow f[i-1][m][s]$,当且仅当$s',s$的第一位相同时不合法.
- 当$j>1$时:
$f[i][j-1][s']\rightarrow f[i][j][s]$
- 边界
- $f[1][m][$初始$]=1$
注意我们只会对单个位进行操作,所以复杂度可以不必额外乘$O(m)$.
复杂度就是$O(nmk^{m+1})$,看起来比较危险,事实上随便去掉一些无用状态(方案数为0)就能跑过去.
```cpp
```
------------
- [P3959 宝藏](https://www.luogu.com.cn/problem/P3959)
认真的子集DP,请自行忽略可以被随机化随便水过的事实……
**题意** : 给出一张带权无向图。
可以钦定一个点作为起点,然后生成一棵树,每条边的代价是到起点的**点数**$\times$**长度**。
问代价最小的生成树。$n\leq 12$ ,时限$\texttt{1s}$
------------
每条边的花费和到起点的点距离有关,我们可以按照`BFS`的方式来DP.
设$f[k][s]$为第$k$轮`BFS`中,已经扩展到的点为$s$的方案数。
每次转移的时候,向外扩展的边默认$k$倍花费,这种决策虽然不能保证每种情况都最优,但是一定不会漏掉最优解。
然后考虑一次性扩展点集$s'$,要计算$s'$到$s$中任意一点距离最小值的和,设为$G[s][s']$。
可以暴力枚举边集计算,复杂度$O(n^2)$,预处理的时候可以使用指针小技巧存储。
方程 : $f[k+1][s]=\max\limits_{s'∩s=\emptyset}f[k][s']+k*G[s][s']$
边界是$f[0][s]=0$ ($s$只含有1个元素)
`DP`的部分是$O(n3^n)$的,瓶颈在预处理的$O(n^23^n)$。
考虑对预处理进行优化,同样可以借用最优子结构。
$G[s][s'+u]=G[s][s']+\min\limits_{v∈s} dis(u,v)$
人话说就是目标集合新增了一个点,起始集合一起来干它。
这样的复杂度就是$O(n3^n)$的了,注意常数。
```cpp
```
另外赠送一个骗分方法。
随机生成一个点的排列,然后按顺序考虑,每次找到最优的边连上。这样的暴力跑一次是$O(n^2)$的。
这样子,总方案数是$n!$,能遇到正解的方案数相当于**遍历序计数**,设为$c$。
每次得到正解的概率是$O(\frac{c}{n!})$,随机$O(\frac{n!}{c})$次则有极大概率得到正解。
总的复杂度就是$O(\frac{n^2n!}{c})$。
对于一棵分叉很多的树,可以感知$c$是相当大的,事实上,$c$最小的就是链形结构。
如果正解是一条链,根在一端,这样$c=1$,我们就挂了。(本题中似乎也很难构造出来?)
事实上,CCF根本没给这种数据,这个骗分随机$50000$次居然直接`AC`了……
------------
- [P5074 Eat the Trees](https://www.luogu.com.cn/problem/P5074)
插头DP入门题。
考虑每个位置能铺成怎样的状态,容易发现只有如下 $6$ 种: (度数为 $2$ 即可)
```cpp
━ ┃ ┛ ┓ ┏ ┗
```
直接枚举一行的状态显然不可承受,考虑填表式轮廓线`DP`.
注意到我们可以只在乎插头,我们用 $2^n$ 记录朝向新区域的插头是否存在。
端点处还有一个侧向插头,需要单独记录。
$f[i][j][s][0/1]$表示填到$i$行$j$列,暴露的插头状态如$s$,侧向插头状态是$0/1$的方案数。
- ① : `━`
当左边**有**插头,上面**没**插头的时候可以填。产生一个向右的插头。
- ② : `┃`
当左边**没**插头,上面**有**插头的时候可以填。产生一个向下的插头。
- ③ : `┛`
当左边和上面都**有**插头的时候可以填。不会产生插头。
- ④ : `┓`
要求同①。产生一个向下的插头。
- ⑤ : `┏`
当左边和上面都**没**插头的时候可以填。会造成向下和向右的插头。
- ⑥ : `┗`
要求同②。会造成向右的插头。
最后一行和右侧是不能留有插头的。
复杂度$O(nm2^n)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define MaxN 270500
using namespace std;
ll f[4100][2],g[4100][2];
#define clear(f,n) {\
for (int i=0;i<(1<<n);i++)\
f[i][0]=f[i][1]=0;\
}
int n,m;
void solve()
{
scanf("%d%d",&n,&m);
clear(f,m);clear(g,m);
f[0][0]=1;
int lim=(1<<m);
for (int i=0;i<n;i++)
for (int j=0,e;j<m;j++){
scanf("%d",&e);
if (e==1){
for (int s=0;s<lim;s++){
if (!(s&(1<<j))){
g[s][1]+=f[s][1];
g[s|(1<<j)][0]+=f[s][1];
g[s|(1<<j)][1]+=f[s][0];
}else {
g[s][0]+=f[s][0];
g[s^(1<<j)][1]+=f[s][0];
g[s^(1<<j)][0]+=f[s][1];
}
}
}else {
for (int s=0;s<lim;s++)
if (!(s&(1<<j)))
g[s][0]=f[s][0];
}
if (j+1==m)
for (int s=0;s<lim;s++)
g[s][1]=0;
swap(f,g);
clear(g,m);
}
printf("%lld\n",f[0][0]);
}
int main()
{
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
```
- [P3272 [SCOI2011]地板](https://www.luogu.com.cn/problem/P3272)
由于我们在从上到下,从左到右填表,对于某个连通块结构,第一次接触时必然在其最靠上靠左的位置。
这样,我们产生的插头方向也就可以确定了,如图。
然后,根据这张图来分析,思路会清楚很多。
若只有一种插头,按照 ②,③ 的拐角,插头是可以拐弯的,但是这会使得一个连通块中有多个弯,显然是不兼容的。
我们只好把插头分成两类 : 未拐过的(红色)和拐过的(蓝色)。如图 :
这样,转移就一目了然了。
(注意,我们约定,凡是存在插头,必须将所在联通快向着所对的方向延伸一格)
- 当左边和上面都没插头
- 如①的拐角,产生两个蓝插头。
- 如②的上方起点,产生一个向下的红插头。
- 如③的右侧起点,产生一个向右的红插头。
- 当左边有蓝插头
- 如①横臂的中段,产生向右的蓝插头。
- 如①横臂的末尾,不产生插头。
- 当上面有蓝插头 : 类似
- 当左边有红插头
- 如③的横臂,产生向右的红插头。
- 如③的拐角,产生向下的蓝插头。
- 当上面有红插头 : 类似
- 当左边和上面都有红插头
- 如④的拐角,不产生插头。
设 $r<c$ ,复杂度为 $O(rc3^r)$。
实现中,为了取址方便,可以使用四进制来存储三进制的插头情况。在滚动数组之后,这部分不是空间瓶颈。
[评测记录](https://www.luogu.com.cn/record/36636721)
- [P5056 【模板】插头dp](https://www.luogu.com.cn/problem/P5056)
和 P5074 的主要区别是,本题要求铺成一整个闭合回路。
我们仅仅记录“是否存在插头”,这一信息足够吗?
对于我们记录的四个插头,可能有如下两种情况。
如果我们按照红色的方案来连接,那么第一种情况是合法的,第二种情况则连成两个圈,不合法。
所以,我们需要记录插头的联通情况,即哪两个插头是相连的。
可以使用最小表示法来标号,然后使用 `hash` 表存储。
这样,由于每次需要将新的最小表示法再次计算并加密,复杂度会多一个 $n$ ,但由于不在常数瓶颈上,往往可以接受。
同时可以发现,插头不会交叉着相连,这样的匹配模式正是括号序列。
但是括号序列的变化就不像最小表示法那样显然了,如果需要追求理论较优的复杂度,可能需要进一步讨论。
当然,暴力重算括号序列也是一种方法。这可以视作以括号序列的方式来 `hash` 的最小表示法。
下面来讨论转移 :
显然,每个格子的度数必须是 $2$。
- 当左边或上面有插头 : 产生向右或向下的同类插头。
- 当左边和上面同时有**异类**插头 : 合并这两个类,不产生插头。
- 没插头 : 产生向右和向下的两个同类插头。
当没有插头时可以作为答案。
```cpp
```
- [P3886 [JLOI2009]神秘的生物](https://www.luogu.com.cn/problem/P3886)
**题意** : 最大权联通块。
由于最后一定要连成一整个联通块,同样需要记录插头的联通情况。
转移 : 每次都可以任意向下或向右产生同类插头。
若只有一个插头进入,合法。
若有两个插头进入,则必须是异类,且会合并这两个类。
注意,如果不产生插头,需要检查一下还有没有剩余其他的同类插头,如果没有,则表示这个联通块结束了。
此时,若还存在异类插头,则不合法。若不存在异类插头,可以向答案贡献,但是不能继续转移。
这里不能使用(经典的)括号序列,只能用最小表示法。
[评测记录] ()
- [P3190 [HNOI2007]神奇游乐园](https://www.luogu.com.cn/problem/P3190)
**题意** : 最大权回路。
显然,每个格子的度数必须是 $2$ 或者 $0$。
- 当左边或上面有插头 : 产生向右或向下的同类插头。
- 当左边和上面同时有异类插头 : 合并这两个类,不产生插头。
- 没插头 : 产生向右和向下的两个同类插头,也可以不产生。
当没有插头时可以作为答案。
[评测记录] ()
- [P4262 [Code+#3]白金元首与莫斯科](https://www.luogu.com.cn/problem/P4262)
**题意** : 给出一个有障碍的矩阵,分别对于每个非障碍点,求出将其变成障碍后,铺 $1\times 2$ 骨牌的方案数(不必铺满)。
先来思考对于一个明确的图,如何计算骨牌铺设方案数。
- 左边或上面有插头 : 不产生插头,骨牌到此为止。
- 无插头 : 可以产生一个向下或向右的插头。
单次 DP 的时间复杂度是 $O(nm2^n)$ 的。
$\rm Subploblem$ : [UVA11270 Tiling Dominoes](https://www.luogu.com.cn/problem/UVA11270)
若枚举障碍格,则复杂度升为 $O(n^2m^22^n)$ ,无法通过。
注意到障碍格只有一个,我们可以正着反着分别做一次 DP,然后合并两个对应的状态,如图:
插头的位置必须是对应的,像对接一样。
这样,复杂度就是 $O(nm2^n)$ 的了,但是空间较大。
[评测记录] ()
------------
附送一些练习题:
- [P1896 [SCOI2005]互不侵犯](https://www.luogu.com.cn/problem/P1896)
- [P2473 [SCOI2008]奖励关](https://www.luogu.com.cn/problem/P2473)
- [P2150 [NOI2015]寿司晚宴](https://www.luogu.com.cn/problem/P2150)