状压DP,即状态压缩DP,它的精髓在于把DP过程中的一个“状态”用一个二进制数巧妙的表示出来。接下来就从一些入门的状压题目来感受一下状压的魅力吧~

[洛谷P5911 [POI2004]PRZ](https://www.luogu.com.cn/problem/P5911 )

大致题意:

$n$个人过最大承载$W$重量的桥,每个人有重量$w_i$与过桥时间$t_i$,多人一组时间取$Max$。求最短过桥时间。

注意数据范围:$100≤W≤400,1≤t≤50,10≤w≤100,1≤n≤16$

有没有注意到$n$的数据范围很耀眼。没错,这就是我们的突破口。

先想暴力记忆化搜索,每个状态记录某些人过桥后的最小时间花费。为了记录状态,我们需要一个$bool$数组,甚至还可以瞎**回溯。

一通乱搞发现,盲目搜索就是过不了


于是来优化吧!

每个状态我们除了用一个数组记录每个人是否加入,还有什么办法吗?

状!态!压!缩!

因为人数比较少,我们可以用一个$n$位的二进制数来记录一个状态。所以这个数转成十进制最大只有$2^{16}$。可以存在数组的一维中。

考虑用$dp[i]$表示状态为$i$下的最少时间花费。它可以由什么状态推导得到呢?

假设当前状态是$0111$,我们可以把它拆成$\{0100,0011\},\{0011,0100\}$另外两个状态。

那么如何枚举呢?这就需要熟练掌握$C++$中的位运算符。很明显,我们要先找到所有被状态$i$包含的状态$j$,包含即$j$中所含的1在$i$中同一个位置一定也是1,但反过来就不一定了。

比如$1010$可以延伸到:$1010,1000,0010,0000$四个状态。

代码怎么实现呢?非常的amazing啊:for(int j=i;j>=0;j=(j-1)&i)

先给状态$j$减去一个1,再和$i$进行按位与,同时保证了不会漏枚和$j$被$i$包含。

那另外一个状态呢?进行 按位异或 就好了。比如上面的$0111⊕0100=0011$,就可以把状态$i$拆成$j$与$i⊕j$两种了。

于是就有了:

$dp[i]=min(dp[i],dp[j]+t[i⊕j])(w[i]<=W)$

其中$t[i]$预处理为状态$i$时的时间花费,$w[i]$预处理为状态$i$时的重量和,初始值$dp[i]=INF$。

于是这道题就完成了。

单一个一维表示状态的题,应该还不算难

$CODE$

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N=(1<<16)+1;
int dp[N],ti[N],we[N];
int t[17],c[17];
int main()
{
    int w,n;
    cin>>w>>n;
    for(int i=1;i<=n;i++)
        scanf("%d%d",&t[i],&c[i]);
    for(int i=0;i<1<<n;i++)
    {
        int d=i,cnt=0;
        while(d)
        {
            cnt++;
            if(d&1)
                ti[i]=max(ti[i],t[cnt]),
                we[i]+=c[cnt];
            d>>=1;
        }
        dp[i]=INF;
    }
    dp[0]=0;
    for(int i=0;i<1<<n;i++)
        for(int j=i;j>=0;j=(j-1)&i)
        {
            if(we[i^j]<=w)dp[i]=min(dp[i],ti[i^j]+dp[j]);
            if(j==0)break;
        }
    printf("%d\n",dp[(1<<n)-1]);
    return 0;
}

POJ-2441 Arrange the bulls

大致题意:

有$N$头牛和$M$个谷仓,每头牛只会选择自己喜欢的谷仓,问有多少种方案可以让每头牛都在自己喜欢的谷仓中。

其中,$1≤N,M≤20$。

一道简单的状压DP但是好像可能会MLE。但是只是练习状压DP的话是一道好题。

考虑用$dp[i][j]$表示状态$i$下,有$j$头牛都选择了合适位置的方案数。状态存储谷仓的选择情况。

所以初值为$dp[0][0]=1$。枚举每一头牛$j$,在$i$状态下如果他喜欢的谷仓$v$被占用了($i\&1<<(v-1)$),那么我们就$dp[i][j]+=dp[i\hat{}1<<(v-1)][j-1]$,即把原有的那头牛移开并把自己放进去,所以把原来的方案数累加上来。

最后$ans=\sum_{i=1}^{2^M} dp[i][n]$。

$CODE$

#include<bits/stdc++.h>
using namespace std;
int dp[1<<20][21];
int a[21];
int s[21][21];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        for(int j=1;j<=a[i];j++)
            scanf("%d",&s[i][j]);
    }
    dp[0][0]=1;
    for(int j=1;j<=n;j++)
        for(int i=1;i<1<<m;i++)
            for(int k=1;k<=a[j];k++)
                if(i&1<<(s[j][k]-1))dp[i][j]+=dp[i^1<<(s[j][k]-1)][j-1];
    int ans=0;
    for(int i=1;i<=1<<m;i++)
        ans+=dp[i][n];
    printf("%d\n",ans);
    return 0;
}

洛谷 P1278 单词游戏

大致题意:

给定$N(N≤16)$个单词,任意选择其中单词,要求为后一个单词的开头必须与前一个单词的末尾字符相同。求最大能选择的单词总长度。

依然状压呗。

设$dp[i][j]$表示$i$状态下以字符$j$结尾的最大单词总长度。其中状态$i$压入了这$N$个单词的选择情况。

当然,首尾字符因为只有五个,我们一一映射到1-5或者0-4是没有问题的,我为了方便,就直接把它们减去'A'作为标识就行了。记$a[j],b[j]$分别标识第$j$个单词的首尾标识,$l[j]$记录第$j$个单词的长度,即对答案的贡献。

再看转移方程。如果当前第$j$个单词没有被选入枚举的状态$i$,那么

$dp[i+2^j][b[j]]=Max\{dp[i+2^j][b[j]],dp[i][a[j]]+l[j] \}$

其中初始值为$dp[2^i][b[i]=l[i]$

注意对于每一个$dp$值,都去对$ans$取个$Max$就好了。

$CODE$

#include<bits/stdc++.h>
using namespace std;
const int N=20;
string x;
int a[N],b[N],l[N];
int f[1<<17][27];
int n;
int main()
{
    scanf("%d",&n);
    int ans=-1;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        a[i]=x[0]-'A',b[i]=x[x.size()-1]-'A',l[i]=x.length();
        f[1<<i][b[i]]=l[i],ans=max(ans,f[1<<i][b[i]]);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int s=0;s<=1<<16;s++)
                if(!(s&1<<j))
                    ans=max(ans,f[s+(1<<j)][b[j]]=max(f[s+(1<<j)][b[j]],f[s][a[j]]+l[j]));
    printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 07 月 27 日 07 : 59 AM