博客详情 - oirush

admin 的博客
状压DP杂谈(+轮廓线,插头)
admin LV 10 SU @ 2026-7-10 11:15:35

状压DP杂谈(+轮廓线,插头) 更新于 2026/7/8 09:30:25 作者

command_block

状压DP思想 : 用集合作为状态,采用特殊的寻址方法。

约定 $cnt(s)=s$ 的二进制中 $1$ 的个数。

P1879 [USACO06NOV]Corn Fields G

这是一道最最最模板的题目了。

题意 : 有一片 $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。

#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。

#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的子集内做减法。

s        : 10101101
s2       : 00101000
s2-1     : 00100111
(s2-1)&s : 00100101

事实上,如果善用剪枝,复杂度会优于 $O(n3^m)$ .

跑n=m=16无障碍矩阵,耗时170ms

#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;
}

两个优化共用并不会带来很大的性能提升,读者可以自行尝试。

轮廓线优化

前面的想法是一行行转移,我们也可以尝试填表式转移。

*****
***##
###..
.....
.....

状态可以这样记录 : $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。

#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。

#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]炮兵阵地

和上一题很类似,只不过相邻距离增加为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)$ ,可过。

#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 染色

轮廓线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)就能跑过去.

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)$ 的了,注意常数。

另外赠送一个骗分方法。

随机生成一个点的排列,然后按顺序考虑,每次找到最优的边连上。这样的暴力跑一次是 $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

插头DP入门题。

考虑每个位置能铺成怎样的状态,容易发现只有如下 $6$ 种: (度数为 $2$ 即可)

━ ┃ ┛ ┓ ┏ ┗

直接枚举一行的状态显然不可承受,考虑填表式轮廓线DP.

注意到我们可以只在乎插头,我们用 $2^n$ 记录朝向新区域的插头是否存在。

端点处还有一个侧向插头,需要单独记录。

$f[i][j][s][0/1]$ 表示填到 $i$ 行 $j$ 列,暴露的插头状态如 $s$ ,侧向插头状态是 $0/1$ 的方案数。

① : ━

当左边有插头,上面没插头的时候可以填。产生一个向右的插头。
② : ┃

当左边没插头,上面有插头的时候可以填。产生一个向下的插头。
③ : ┛

当左边和上面都有插头的时候可以填。不会产生插头。
④ : ┓

要求同①。产生一个向下的插头。
⑤ : ┏

当左边和上面都没插头的时候可以填。会造成向下和向右的插头。
⑥ : ┗

要求同②。会造成向右的插头。

最后一行和右侧是不能留有插头的。

复杂度 $O(nm2^n)$ 。

#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]地板

由于我们在从上到下,从左到右填表,对于某个连通块结构,第一次接触时必然在其最靠上靠左的位置。

这样,我们产生的插头方向也就可以确定了,如图。

然后,根据这张图来分析,思路会清楚很多。

若只有一种插头,按照 ②,③ 的拐角,插头是可以拐弯的,但是这会使得一个连通块中有多个弯,显然是不兼容的。

我们只好把插头分成两类 : 未拐过的(红色)和拐过的(蓝色)。如图 :

这样,转移就一目了然了。

(注意,我们约定,凡是存在插头,必须将所在联通快向着所对的方向延伸一格)

当左边和上面都没插头
- 如①的拐角,产生两个蓝插头。
- 如②的上方起点,产生一个向下的红插头。
- 如③的右侧起点,产生一个向右的红插头。
当左边有蓝插头
- 如①横臂的中段,产生向右的蓝插头。
- 如①横臂的末尾,不产生插头。
当上面有蓝插头 : 类似
当左边有红插头
- 如③的横臂,产生向右的红插头。
- 如③的拐角,产生向下的蓝插头。
当上面有红插头 : 类似
当左边和上面都有红插头
- 如④的拐角,不产生插头。

设 $r<c$ ,复杂度为 $O(rc3^r)$ 。

实现中,为了取址方便,可以使用四进制来存储三进制的插头情况。在滚动数组之后,这部分不是空间瓶颈。

评测记录

P5056 【模板】插头dp

和 P5074 的主要区别是,本题要求铺成一整个闭合回路。

我们仅仅记录“是否存在插头”,这一信息足够吗?

对于我们记录的四个插头,可能有如下两种情况。

如果我们按照红色的方案来连接,那么第一种情况是合法的,第二种情况则连成两个圈,不合法。

所以,我们需要记录插头的联通情况,即哪两个插头是相连的。

可以使用最小表示法来标号,然后使用 hash 表存储。

这样,由于每次需要将新的最小表示法再次计算并加密,复杂度会多一个 $n$ ,但由于不在常数瓶颈上,往往可以接受。

同时可以发现,插头不会交叉着相连,这样的匹配模式正是括号序列。

但是括号序列的变化就不像最小表示法那样显然了,如果需要追求理论较优的复杂度,可能需要进一步讨论。

当然,暴力重算括号序列也是一种方法。这可以视作以括号序列的方式来 hash 的最小表示法。

下面来讨论转移 :

显然,每个格子的度数必须是 $2$ 。

当左边或上面有插头 : 产生向右或向下的同类插头。
当左边和上面同时有异类插头 : 合并这两个类,不产生插头。
没插头 : 产生向右和向下的两个同类插头。

当没有插头时可以作为答案。

P3886 [JLOI2009]神秘的生物

题意 : 最大权联通块。

由于最后一定要连成一整个联通块,同样需要记录插头的联通情况。

转移 : 每次都可以任意向下或向右产生同类插头。

若只有一个插头进入,合法。

若有两个插头进入,则必须是异类,且会合并这两个类。

注意,如果不产生插头,需要检查一下还有没有剩余其他的同类插头,如果没有,则表示这个联通块结束了。

此时,若还存在异类插头,则不合法。若不存在异类插头,可以向答案贡献,但是不能继续转移。

这里不能使用(经典的)括号序列,只能用最小表示法。

[评测记录] ()

P3190 [HNOI2007]神奇游乐园

题意 : 最大权回路。

显然,每个格子的度数必须是 $2$ 或者 $0$ 。

当左边或上面有插头 : 产生向右或向下的同类插头。
当左边和上面同时有异类插头 : 合并这两个类,不产生插头。
没插头 : 产生向右和向下的两个同类插头,也可以不产生。

当没有插头时可以作为答案。

[评测记录] ()

P4262 [Code+#3]白金元首与莫斯科

题意 : 给出一个有障碍的矩阵,分别对于每个非障碍点,求出将其变成障碍后,铺 $1\times 2$ 骨牌的方案数(不必铺满)。

先来思考对于一个明确的图,如何计算骨牌铺设方案数。

左边或上面有插头 : 不产生插头,骨牌到此为止。
无插头 : 可以产生一个向下或向右的插头。

单次 DP 的时间复杂度是 $O(nm2^n)$ 的。

$\rm Subploblem$ : UVA11270 Tiling Dominoes

若枚举障碍格,则复杂度升为 $O(n^2m^22^n)$ ,无法通过。

注意到障碍格只有一个,我们可以正着反着分别做一次 DP,然后合并两个对应的状态,如图:

插头的位置必须是对应的,像对接一样。

这样,复杂度就是 $O(nm2^n)$ 的了,但是空间较大。

[评测记录] ()

附送一些练习题:

状压DP杂谈(+轮廓线,插头)

状态

开发

支持

关于

状压DP杂谈(+轮廓线,插头)

状态

开发

支持

关于

还没有账户？

登录