状态压缩

· · 个人记录

设置状态。

有 n 个因素，每个有 p 种状态，则空间大小 p^n，存在 p^{i-1}+q 代表 i 的第 q 个状态。然后就可以转移了。

例题

思路：设 f_{i,j} 表示 i 状态最后停在 j(0\le j\lt n) 的最短路，有转移：

f_{i|2^j,j}=\min\limits_{k=1}^{n}f_{i,k}+dis_{k,j}

但必须保证 k 存在于 i 这个状态才取 \min。

#include<bits/stdc++.h>
#define il inline
#define re register
using namespace std;

const int N=20;

int n,dp[1<<N][N],dis[N][N],ans;

int main() {
    scanf("%d",&n);
    for(re int i=0;i<n;i++) {
        for(re int j=0;j<n;j++) {
            scanf("%d",&dis[i][j]);
        }
    }
    memset(dp,0x3f,sizeof dp);
    dp[1][0]=0;
    for(re int i=1;i<=(1<<n)-1;i++) {
        for(re int j=0;j<n;j++) {
            if((i&(1<<j))) continue;
            for(re int k=0;k<n;k++) {
                if(!(i&(1<<k))) continue;
                dp[i|(1<<j)][j]=min(dp[i|(1<<j)][j],dp[i][k]+dis[k][j]);
            }
        }
    }
    ans=2e9+10;
    for(re int i=0;i<n;i++) {
        ans=min(ans,dp[(1<<n)-1][i]+dis[i][0]);
    }
    printf("%d\n",ans);
    return 0;
}

练习题

思路与上面的题目很相似，只需注意可以从任意单词开始并且首尾相连。

#include<bits/stdc++.h>
#define il inline
#define re register
using namespace std;

const int N=16;

int n,st[N],en[N],l[N],dp[1<<N][N],ans;

char s[101];

int main() {
    scanf("%d",&n);
    for(re int i=0;i<n;i++) {
        scanf("\n%s",s);
        l[i]=strlen(s);
        st[i]=s[0]-'A'+1;
        en[i]=s[l[i]-1]-'A'+1;
    }
    for(re int i=0;i<n;i++) {
        ans=max(ans,dp[1<<i][i]=l[i]);
    }
    for(re int i=1;i<=(1<<n)-1;i++) {
        for(re int j=0;j<n;j++) {
            if(i&(1<<j)) continue;
            for(re int k=0;k<n;k++) {
                if(!(i&(1<<k))) continue;
                if(en[k]^st[j]) continue;
                ans=max(ans,dp[i|(1<<j)][j]=max(dp[i|(1<<j)][j],dp[i][k]+l[j]));
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

例题

经过观察，一行可行的状态只和上一行有关。

于是可以枚举。判断某个状态与上行某个状态是否包容时需要用到位运算。详见代码。

#include<bits/stdc++.h>
#define il inline
#define re register
using namespace std;

const int N=10;

int n,k,cnt,good[1<<N],bad[1<<N];

long long dp[N][1<<N][N*N],ans;

il void dfs(re int level,re int state,re int sum) {
    if(level>=n) {
        dp[0][++cnt][sum]=1;
        good[cnt]=state;
        bad[cnt]=sum;
        return ;
    };
    dfs(level+1,state,sum);
    if(level==0||!(state&(1<<level-1))) dfs(level+1,state+(1<<level),sum+1);
}

int main() {
    scanf("%d%d",&n,&k);
    dfs(0,0,0);
    for(re int i=1;i<n;i++) {
        for(re int j=1;j<=cnt;j++) {
            for(re int k=1;k<=cnt;k++) {
                if(good[j]&good[k]
                ||(good[j]<<1)&good[k]
                ||good[j]&(good[k]<<1)) continue;
                // 若有相同位都有王，跳过。
                for(re int u=0;u<=n*i-bad[j];u++) {
                    dp[i][j][u+bad[j]]+=dp[i-1][k][u];
                }
            }
        }
    }
    for(re int i=1;i<=cnt;i++) {
        ans+=dp[n-1][i][k];
    }
    printf("%lld\n",ans);
    return 0;
}

练习题

这题其实相当于上题的一个弱化版，但需要多处理“不能种草的土地”。怎么办呢？

假设对于第 i 行全选贫瘠土地的状态为 f_i。现在枚举到这一行考虑的状态为 g，则当且仅当 f_i\And g=0 时是满足条件的。这就很容易处理了，45 行轻松搞定。

#include<bits/stdc++.h>
#define il inline
#define re register
using namespace std;

const int N=12,mod=1e8;

int n,m,a,f[N],good[1<<N],cnt,dp[N][1<<N],ans;

il void dfs(re int level,re int state) {
    if(level>=m) {
        good[++cnt]=state;
        if(!(state&f[0])) dp[0][cnt]=1;
        return ;
    }
    dfs(level+1,state);
    if(level==0||!(state&(1<<level-1))) dfs(level+1,state|(1<<level));
}

int main() {
    scanf("%d%d",&n,&m);
    for(re int i=0;i<n;i++) {
        for(re int j=0;j<m;j++) {
            scanf("%d",&a);
            if(!a) f[i]|=(1<<j);
        }
    }
    dfs(0,0);
    for(re int i=1;i<n;i++) {
        for(re int j=1;j<=cnt;j++) {
            for(re int k=1;k<=cnt;k++) {
                if(good[j]&f[i]||good[j]&good[k]) continue;
                dp[i][j]+=dp[i-1][k];
                if(dp[i][j]>=mod) dp[i][j]-=mod;
            }
        }
    }
    for(re int i=1;i<=cnt;i++) {
        ans+=dp[n-1][i];
        if(ans>=mod) ans-=mod;
    }
    printf("%d\n",ans);
    return 0;
}