状压DP复习笔记

更好的阅读体验

前言

复习笔记第4篇。CSP RP++。

引用部分为总结性内容。

注：我不知道为啥 AcWing 的 LaTeX没有 \and 这种东西……将就着看吧，反正就一道题写了这个（

0——P1433 吃奶酪

题目链接 luogu

题意

房间里放着 $n$ 块奶酪，要把它们都吃掉，问至少要跑多少距离？一开始在 $(0,0)$ 点处。 $n\leq 15$ ,保留两位小数。

思路

为啥状压第一题是绿题啊。这么水了吗，为啥我还不会（

令 $f[i][s]$ 表示从点 $i$ 出发，遍历集合为 $S$ 的最小值，枚举其他点进行转移。预处理边界 $f[i][s]=0$ （$S$ 为除了第 $i-1$ 位均为 $0$ 的点集的二进制表示），注意加上 $i\to (0,0)$ 。

复杂度 $O(n^2 \times 2^n)$

由此题可以看出，状压DP由于需要设 $2^n$ 种状态，所以 $n$ 的大小通常不会很大

这个特点在矩阵乘法加速的复习中也有提到。根据不同的需要选择即可。

矩乘主要是用于加速递推，而状压主要是在DP原来的 “只存最优值和关键值” 的基础上，需要知道具体状态的一种方式。两种差别还是很大的。

代码

#include <bits/stdc++.h>
#define lb double
using namespace std;
const int N=21;
lb x[N],y[N],f[N][35000];
int n;

lb get_dis( int a,int b )
{
    return sqrt( (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}

int main()
{
    scanf( "%d",&n );
    for ( int i=1; i<=n; i++ )
        scanf( "%lf%lf",&x[i],&y[i] );

    memset( f,127,sizeof(f) );
    for ( int s=1; s<=(1<<n)-1; s++ )   //枚举集合
     for ( int i=1; i<=n; i++ )     
     {
        if ( (s&(1<<(i-1)))==0 ) continue;      //根本就没经过，不可能是起点
        if ( s==(1<<i-1) ) { f[i][s]=0; continue;}
        for ( int j=1; j<=n; j++ )
        {
            if ( (s&(1<<(j-1)))==0 || i==j ) continue;
            f[i][s]=min( f[i][s],f[j][s-(1<<(i-1))]+get_dis(i,j) ); 
        }
     }
    lb ans=-1;
    for ( int i=1; i<=n; i++ )
    {
        lb s=f[i][(1<<n)-1]+get_dis(i,0);       //加上到起点的距离，不过放在初始化应该也没问题
        if ( ans==-1 || ans>s ) ans=s;
    }

    printf( "%.2lf",ans );

    return 0;
}

1——P5911 [POI2004]PRZ

题目链接 luogu

题意

给定桥能承受的最大重量 $W$ ,队员体重 $w_i$ ，队员通过时间 $t_i$ ，每一组通过的时间为最慢的一个。问最小总时间。

思路

非常典型的一道枚举子集状压。

重点在于枚举子集的代码：

for ( int S1=S; S1!=0; S1=(S1-1)&S )    //S1是子集，S是总集，S2是S1对于S的补集
    S2=S^S1;

考虑如何证明这样枚举了所有的子集。

首先，对于 $x<y$ ，显然有 $x\and y \in y$ . 那么可以知道，$(S1-1)\and S$ 一定是 $S$ 的子集。

然后，对于 $S1-1$ ，它显然是第一个比 $S1$ 小的集合，然后对 $S$ 做 $\and $ 操作，那么就是 “比 $S1$ 小的第一个 $S$ 的子集”，这样可以保证枚举完所有的子集。

或者，先考虑特殊情况，即 $S=2^i$ 。这个时候，显然有子集 $S1=S1-1$ 这样的操作可以枚举子集。那么现在也是一样，首先同样地 $-1$ ，然后 $\and S$ 保证是 $S$ 的子集，在 $S=2^i$ 的情况下比 $S1$ 小的第一个子集去掉不合法的1，显然不会比其他的子集更小。

然后对于这道题，预处理每种状态（单独成一组过桥），然后状压即可。

#include <bits/stdc++.h>
using namespace std;
const int N=(1<<16)+1,inf=0x3f3f3f3f;
int W,n,w[21],t[21];
int ti[N],wi[N],f[N];

void init()
{
    for ( int i=0; i<(1<<n); i++ )
    {
        int dig=i,cnt=0;
        while ( dig )
        {
            cnt++;
            if ( dig&1 ) wi[i]+=w[cnt],ti[i]=max( ti[i],t[cnt] );
            dig>>=1;
        }
        f[i]=inf;
    }
}

int main()
{
    scanf( "%d%d",&W,&n );
    for ( int i=1; i<=n; i++ )
        scanf( "%d%d",&t[i],&w[i] );

    init(); f[0]=0;
    for ( int i=0; i<(1<<n); i++ )
     for ( int j=i; j>=0; j=i&(j-1) )
     {
        if ( wi[i^j]<=W ) f[i]=min( f[i],f[j]+ti[i^j] );
        if ( j==0 ) break;
     }

    printf( "%d",f[(1<<n)-1] );

    return 0;
}

2——P1879 [USACO06NOV]Corn Fields G

题目链接 luogu

题意

一块长方形的牧场，M行N列，每一格都是一块正方形的土地，在上面种草。有些土地相当贫瘠，不能用来种草。没有哪两块草地有公共边。求一共有多少种种植方案。

思路

考虑不同行之间的转移（显然，直接存下 $144$ 位的二进制并不现实），$f[i][j]$ 为当前行 $i$ ，状态为 $j$ 。

每次转移的时候判断：和被转移的上一行状态是否冲突；这一行本身是否冲突。显然这两个都可以预处理掉。最后，由于每次由上一行转移过来，所以要预先求出第一行的状态（没有上一行的限制，只需要算本行不能放的即可。）

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4100,mod=1e8;
int f[15][N],lin[N],pd[N],mp[15][15],n,m;

int main()
{
    scanf( "%d%d",&m,&n );
    int num=(1<<n)-1;
    for ( int i=1; i<=m; i++ )
     for ( int j=1; j<=n; j++ )
        scanf( "%d",&mp[i][j] );

    for ( int i=1; i<=m; i++ )
     for ( int j=1; j<=n; j++ )
        lin[i]=(lin[i]<<1)+(mp[i][j] ? 0 : 1);
    //当前行不能放 
    int cnt=0;
    for ( int i=0; i<=num; i++ )
    {
        if ( i&(i>>1) ) continue;
        pd[++cnt]=i;        //确保同行的不相邻 
    }
    int now,las;
    for ( int i=1; i<=cnt; i++ )    //第一行init 
    {
        now=pd[i];
        if ( pd[i]&lin[1] ) continue; 
        f[1][i]=1;
    }
    for ( int i=2; i<=m; i++ )
     for ( int j=1; j<=cnt; j++ )
     {
        las=pd[j];          //上一行 
        if ( las&lin[i-1] ) continue;       //上一行不行 
        for ( int k=1; k<=cnt; k++ )
        {
            now=pd[k];
            if ( now&lin[i] ) continue;     //本身不行 
            if ( now&las ) continue;        //和上一行冲突 
            (f[i][k]+=f[i-1][j])%=mod;
        }
     }

    int ans=0;
    for ( int i=1; i<=cnt; i++ )
        (ans+=f[m][i])%=mod;
    printf( "%d",ans );

    return 0;
}

3——P3052 [USACO12MAR]Cows in a Skyscraper G

题目链接 luogu

题意

给出 $n$ 个物品，体积为 $w[i]$，现把其分成若干组，要求每组总体积 $<=W$，问最小分组数。$n<=18$

思路

状压显然。用 $f[i]$ 记录当前状态为 $i$ 时，所需要的最小组数。$v[i]$ 表示状态 $i$ 下，没满的那一组剩余体积。转移时判断 $v[i]$ 和 $a[j]$ 的大小即可。

注意此题有一些细节，见代码注释。

#include <bits/stdc++.h>
using namespace std;
const int N=21,M=(1<<N);
int n,W,f[M],v[M],a[N];

int main()
{
    scanf( "%d%d",&n,&W );
    for ( int i=1; i<=n; i++ )
        scanf( "%d",&a[i] );

    memset( f,0x3f,sizeof(f) );
    f[0]=1; v[0]=W;
    for ( int i=0; i<(1<<n); i++ )
     for ( int j=1; j<=n; j++ )
     {
        if ( i&(1<<j-1) ) continue;
        if ( a[j]<=v[i] && f[i|(1<<j-1)]>f[i] )
        {
            f[i|(1<<j-1)]=f[i]; 
            v[i|(1<<j-1)]=v[i]-a[j];    
        }
        if ( a[j]<=v[i] && f[i|(1<<j-1)]==f[i] )
            v[i|(1<<j-1)]=max( v[i|(1<<j-1)],v[i]-a[j] );
        //一开始没加这个特判……不仅是f[i]需要取最优，在f[i]相同的情况下，
        //剩余空间越大显然也更优。
        if ( a[j]>v[i] && f[i|(1<<j-1)]>=f[i]+1 )
        {
            f[i|(1<<j-1)]=f[i]+1;
            v[i|(1<<j-1)]=max( v[i|(1<<j-1)],W-a[j] );
            //新建了一组，但是至于“当前组”选哪一组是可以max的
            //因为上一组也没放满 
        }
     }

    printf( "%d",f[(1<<n)-1] ); 
    return 0;
}

4——P5640 【CSGRound2】逐梦者的初心

题目链接 luogu

题意

给你一个长度为 $n$ 的字符串 $S$。有 $m$ 个操作，保证 $m\le n$ 。你还有一个字符串 $T$，刚开始为空。共有两种操作。

第一种操作：在字符串 $T$ 的末尾加上一个字符。

第二种操作：在字符串 $T$ 的开头加上一个字符。

每次操作完成后要求输出有几个 $l \in [1,T.size]$ 满足以下条件：

对于 $\forall i \in [1,l]$ 有 $T_{T.size-l+i} \ne S_{i}$

Tip:字符串下标从 $1$ 开始。$T.size$ 表示 $T$ 的长度。

思路

由于每个位置和每种字符都是独立的，对每种字符都记录一下位子，用 $f [i]=0/1$ 表示长度为 $i$ 的后缀是否合法，$0$ 表示可以，$1$ 表示不行。于是bitset优化就比较明显了。

在末尾加一个字符时，左移一位做 or 运算，因为状态由 $i-1$ 的情况加上新的一位转移过来。

在开头加一个字符时，直接or上该字符出现的状态左移长度减一位，因为开头加入字符，那么后面的所有字符后移一位。这里需要费用提前的思想，即每次加入字符时，将所有能贡献到答案的位置一次存好。考虑如何进行。设 $ch$ 在第 $i$ 位加入，那么离末尾的长度是 $i-1$ .设 $ch$ 对应的 $id$ 在第 $k$ 位是1，那么取到第 $k$ 位一定不合法，这时候 $ch$ 的位置由队尾左移 $i-1$ 位得到，所以当 $ch\to k$ 的时候，$tail\to k-l+1$ ,由于存储是倒序的，所以有 f=f|(id[ch]<<(i-1));

答案就是范围内 $0$ 的个数。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,opt,s[N],ch;
bitset<35010> f,id[1010],now;

int main()
{
    scanf( "%d%d",&n,&m );
    for ( int i=1; i<=n; i++ )
        scanf( "%d",&s[i] );

    for ( int i=1; i<=m; i++ )
        id[s[i]].set(i);
    now.set();
    for ( int i=1; i<=m; i++ )
    {
        scanf( "%d%d",&opt,&ch );

        now.reset(i);
        if ( opt==0 ) f=(f<<1)|id[ch];
        else f=f|(id[ch]<<(i-1));

        printf( "%d\n",(~(f|now)).count() );
    }
    return 0;
}

5——P2704 [NOI2001]炮兵阵地

题目链接 luogu AcWing

题意

一个 $N\times M$ 的地图，每一格是山地（H）或平原（P）. 每一格平原地形上可以布置一支炮兵部队（山地上不能部署）.如果在地图中的平原上部署一支炮兵部队，则它能攻击到的区域：沿横向左右各两格，沿纵向上下各两格。攻击范围不受地形的影响。 现在，保证任何一支炮兵部队都不在其他支炮兵部队的攻击范围内，求最多能放的炮兵数量。 $N\leq 100,M\leq 10$

思路

一个很显然的想法是，既然炮兵的攻击范围是两行，那么每个 $dp$ 状态就放当前行，上面两行就好了。不幸的是，由于 $N$ 比较大，这样开状态就 MLE了。所以考虑如何得知上两行的状态。然后就会发现，如果状态只存储当前行号 $x$，当前状态 $i$ ，以及上一行的状态 $j$ ，那么在转移的时候通过 $j$ 可以得到 $x-1$ 行的“当前状态”，而 $x-2$ 行的 “当前状态” 可以通过 $x-1$ 行的 “上一行状态” 得到，那么问题就解决了，只需要存两个状态。但是开整个地图显然不现实，所以还需要加滚动数组，也就是只存储当前行、上一行的状态，每次 $\mod 2$ 即可。这样就完整地解决了空间问题。

用 $f[L][S][i]$ 表示当前是第 $i$ 行，这一行状态是 $S$ ,上一行状态是 $L$ ,那么
$$ f[L][S][i]=max(f[L][S][i],f[F][L][i-1]+sum[S]); $$
$sum[S]$ 表示 $S$ 这个状态 $1$ 的个数（即炮兵的个数）

实现时注意细节，上文中并没有考虑地形是否合法的问题，这个可以预处理出来。还有每一行之内的合法状态，每一个合法状态对应的 $sum$ 都需要预处理，这样可以只枚举合法状态，大大减少循环次数。

#include <bits/stdc++.h>
using namespace std;
const int N=110,M=11,S=1<<M;
int n,m,g[N],f[2][S][S],cnt[S];
vector<int> state;

bool check( int s )
{
    for ( int i=0; i<m; i++ )
        if ( (s>>i&1) && ( (s>>i+1&1) || (s>>i+2&1) ) ) return 0;
    return 1; 
}

int count( int s )
{
    int res=0;
    for ( ; s; s>>=1 )
        res+=(s&1);
    return res;
}

int main()
{
    scanf( "%d%d",&n,&m );
    for ( int i=0; i<n; i++ )
     for ( int j=0; j<m; j++ )
     {
        char ch; cin>>ch;
        if ( ch=='H' ) g[i]+=(1<<j);
     }

    for ( int i=0; i<(1<<m); i++ )
        if ( check(i) ) state.push_back(i),cnt[i]=count(i);
    for ( int i=0; i<=n+1; i++ )
     for ( int j=0; j<state.size(); j++ )
      for ( int k=0; k<state.size(); k++ )
       for ( int u=0; u<state.size(); u++ )
       {
        int t1=state[u],t2=state[j],t3=state[k];
        if ( (t1&t2) || (t1&t3) || (t2&t3) ) continue;
        if ( g[i]&t3 ) continue; 
        f[i&1][j][k]=max( f[i&1][j][k],f[i-1&1][u][j]+cnt[t3] );
       }

    printf( "%d",f[n+1&1][0][0] );
}

6——P3959 宝藏

题目链接 luogu AcWing

题意

藏宝图上标出了 $n$ 个宝藏屋， 和这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度，起点任意。

已有道路可以0代价通行，每开凿一条新的道路，就会挖掘出该道路所能到达的宝藏屋的宝藏，不会开发两个已经被挖掘的屋子之间的道路。新开发一条道路的代价是：
$$ \mathrm{L} \times \mathrm{K} $$
$L$ 代表这条道路的长度，$K$ 代表从最初的起点到这条道路的起点所经过的宝藏屋的数量（包括头尾） 。

求工程总代价最小值。

思路

状压，状态存储：已经连通的点集。

令 $f[i][j][k]$ 表示状态为 $j$ ，深度为 $k$ （第 k 层），第 $i$ 个点加入的代价。（$k$ 的加入是为了防止做到后面的时候前面的层还没有更新，避免了深度混乱的情况）

然后考虑记忆化搜索。参数：当前状态 $now$ ，总代价 $sum$ ，深度 $dep$ ，每次用当前状态中已经有的点更新其他的点并加入状态。答案就是点集 $=U$ 的最小代价。

细节：需要加一些剪枝，比如当前解比当前最优解大了直接return，因为之后的解只增不减。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=15,inf=1e9+7;
int n,m,lim,ans=inf,mp[N][N],dis[N],f[N][5010][N];

void dfs( int now,int sum,int dep )
{
    if ( sum>=ans ) return;
    if ( now==lim ) { ans=min( ans,sum ); return; }
    for ( int i=1; i<=n; i++ )
     if ( 1<<(i-1)&now )
        for ( int j=1; j<=n; j++ )
            if ( !(1<<(j-1)&now) && mp[i][j]<inf )
            {
                if ( f[j][1<<(j-1)|now][dep+1]<=sum+dis[i]*mp[i][j] ) continue;
                f[j][1<<(j-1)|now][dep+1]=sum+dis[i]*mp[i][j];
                dis[j]=dis[i]+1;
                dfs( 1<<(j-1)|now,f[j][1<<(j-1)|now][dep+1],dep+1 );
            }
}

int main()
{
    scanf( "%d%d",&n,&m );
    lim=(1<<n)-1; memset( mp,inf,sizeof(mp) ); 
    for ( int i=1,u,v,w; i<=m; i++ )
    {
        scanf( "%d%d%d",&u,&v,&w );
        mp[u][v]=mp[v][u]=min( mp[u][v],w );
    }

    for ( int i=1; i<=n; i++ )
    {
        memset( dis,0,sizeof(dis) ); memset( f,inf,sizeof(f) );
        dis[i]=1; dfs( 1<<(i-1),0,0 );
    }

    printf( "%d",ans );
    return 0;
}

7——P1357 花园

题目链接 luogu

题意

有一座环形花园，顺时针方向编号为 $1 \sim n$ 。花园 $1$ 和 $n$ 相邻。任意相邻 $m$ 个花圃中都只有不超过 $k$ 个 C 形的花圃，其余花圃均为 P 形的花圃。求出符合规则的花园种数对 $1e9+7$ 取模的结果。

$ 2 \leq n \le 10^{15}，2 \leq m \leq \min(n, 5)$

思路

（以上数据范围为 $100$ ）如果只是 80 分做法，那么显然，根据 $m\leq 5$ 的范围，可以想到状压（因为只有两种状态，为 c 或是为 P ），特别处理环形即可。

现在考虑如何从 $n\leq 1e5\to n\leq 1e{15}$ .对于这个范围，首先盲猜一个可以接受的复杂度，必须是 $O(\sqrt n)$ 或是 $O(\log n)$ 。根号做法一般都是分块之类的方法，在 状压DP 上能优化的可能性不大；那么考虑是否存在一个 $\log n$ 做法。看到 $\log n+DP$ ，首先会想到矩乘加速。

以上是口胡的大致思路，现在来具体分析整个 DP 方程和转移 base。

首先考虑简单状压。对于一个新的花园，受到之前 $m-1$ 个花园的样式限制，那么状态就是 $S$ ，表示当前 $m$ 个连续花园的样式情况。每次转移的时候相当于在原来的状态后面加了一位，令 $dp[i][s]$ 表示目前在第 $i$ 个花园，左侧 $m$ 个状态为 $S$ 的方案数。那么方程就是：

$$ dp[i][s]=dp[i-1][(s>>1)+2^{m-1}]+dp[i-1][s>>1]. $$

dfs 预处理出所有可能状态。然后处理环形。令 $dp[m][S]=1$ ，然后转移到 $dp[n+m]$ ，把 $dp[n+m][S]$ 累加到答案。因为前 $m$ 个花圃等同于 $n+1\to m.$

然后考虑如何得到转移矩阵 $base.$

首先，浪费一层循环以化简这个式子：

$$ dp[i][j]=\sum dp[i-1][k] $$

但是这样还要考虑状态能否转移的问题。所以不如再来一个数组 $pd[k][j]$ 表示状态 $k$ 能否转移到 $j$.改写式子：

$$ dp[i][j]=dp[i-1][k]\times pd[k][j] $$

然后就愉快地发现，这是个标准的矩乘式子，连推都不需要就得到了一个现成的 $base.$

然而还没有结束！我们还没有得到最终的答案。继续思考，我们最终的答案是对于每一个状态 $S$ ，取 $dp[n+m][S]$ ，也就是说，是 $dp$ 矩乘上 $pd$ 第 $S$ 列的和。把 $dp$ 数组缩减到一维，并且做矩阵乘法，那么就会发现，最终结果等同于乘上 $pd$ 的对角线部分。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+10,mod=1e9+7;
ll n,m,K,status[40],cnt=0,vis[40];
struct matrix
{
        ll mt[40][40];
        matrix () { memset( mt,0,sizeof(mt) ); }
        void reset()
        {
                memset( mt,0,sizeof(mt) );
                for ( ll i=0; i<=32; i++ )
                        mt[i][i]=1;
        }
        matrix operator * ( const matrix b )
        {
                matrix c;
                for ( ll i=0; i<=32; i++ )
                 for ( ll j=0; j<=32; j++ )
                  for ( ll k=0; k<=32; k++ )
                        c.mt[i][j]=(c.mt[i][j]+mt[i][k]*b.mt[k][j])%mod;
                return c;
        }
}ans,base;

bool check( ll s )
{
        ll res=0;
        for ( ; s; s>>=1 )
                if ( s&1 ) res++;
        return res<=K;
}

void dfs( ll x,ll S )
{
        if ( x==m )
        {
                if ( check(S) )
                {
                        status[++cnt]=S; base.mt[(S>>1)+(1<<(m-1))][S]=1;
                        base.mt[S>>1][S]=1; vis[S]=1;
                }
                return;
        }
        dfs( x+1,S ); dfs( x+1,S+(1<<x) );
}

matrix power( matrix a,ll b )
{
        matrix res; res.reset();
        for ( ; b; b>>=1,a=a*a )
                if ( b&1 ) res=res*a;
        return res;
}

signed main()
{
        scanf( "%lld%lld%lld",&n,&m,&K );

        dfs( 0,0 ); ans=power( base,n );
        ll sum=0;
        for ( ll i=0; i<=32; i++ )
                if ( vis[i] ) (sum+=ans.mt[i][i])%=mod;

        printf( "%lld",sum );
}

Last

To be continue…… Maybe.