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

command_block · 2020-03-09 09:32:06 · 个人记录

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

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

• P1879 [USACO06NOV]Corn Fields G

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

题意 : 有一片 n\times m 的土地,若干位置不能种菜,不能在相邻的土地种菜,求种菜的方案数。

边界 : 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 串的,我们来计数一下:

代换一下能得到这就是个斐波那契数列……

复杂度就是 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的方案数。

暴露出来的部分即为图中#。

这样定义状态有什么好处呢?

前面我们是一次性转移一行,目标状态十分庞大,现在是一次填写一个,目标状态就很小了。

只有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,而且求的是最大值。

这时我们就要记录两层的状态。

设 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 种颜色中的一种,要求相邻的格子颜色不同。

给定第一行与最后一行的染色,求总染色方案数。

这题毒瘤之处在于,有一个点 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

• 当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)。

考虑对预处理进行优化,同样可以借用最优子结构。

人话说就是目标集合新增了一个点,起始集合一起来干它。

这样的复杂度就是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 记录朝向新区域的插头是否存在。

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