状态压缩dp

· · 个人记录

前置知识

按位与 &

两个数在二进制下按位比较，只有两个数完全相同的时候才会返回1，常用于取某一位

按位或 |

两个数只要有一位是1返回1，常用于合并集合

按位异或 ^

不同为1，相同为0，常用于去重，找不同

按位取反 ~

用的比较少，将所有位取反（符号位也会所以要小心补码）

左移/右移 <</>>

将一个数的二进制位向左或者向右移，相当于*或÷2

状压dp

将状态用二进制压缩起来，一般作为选和不选问题的上位替代
如对于选与不选，可以将选和不选用1/0来代替，再根据这条来转化成二进制，另外创建一个维度来存储二进制长度，如10可以转化成1010表示为选1，3不选2，4，这样，原本要用数组存一大堆「哪些被选过」的信息，现在只用一个整数就能表示，节省空间，方便转移。

P1171

板子题直接套

#include<bits/stdc++.h>
using namespace std;
const int maxn = 21;
int dp[(1<<21)-1][maxn],dis[maxn][maxn];
int n;
int main() {        
        cin>>n;
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                cin>>dis[i][j];
            }
        }
        memset(dp,0x3f,sizeof(dp));
        dp[1][0]=0;
        for(int status=2;status<(1<<n);status++) {
            for(int i=0;i<n;i++) {
                if((status>>i)&1) {
                    for(int j=0;j<n;j++) {
                        int tmp=status^(1<<i);
                        if(i!=j&&(tmp>>j)) {
                            dp[status][i]=min(dp[status][i],dp[tmp][j]+dis[j][i]);
                        }
                    }
                }
            }
        }
        int ans=INT_MAX;
        for(int i=0;i<n;i++) {
            ans=min(ans,dp[(1<<n)-1][i]+dis[i][0]);
        }
        cout<<ans;
        return 0;
}

P1879

首先读题得出来三个条件
贫瘠的土地不能种草
一头奶牛一块草地
两块草地不能连在一起
根据这些条件，我们可以先把草地是否贫瘠转成10状态然后再使用状压dp压缩状态，最后枚举每一行进行判断看是否能放置奶牛就行
注意存储的时候要取反
判断和状态转移方程：

if(status1&(status1<<1)) {
                continue;
            }
            if((status1&f[i])!=0) {
                continue;
            }
            for(int status2=0; status2<(1<<m); status2++) {
                if(status1&status2) {
                    continue;
                }
                dp[status1][i]+=dp[status2][i-1];
                dp[status1][i]%=mod;
            }
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e8;
const int maxn = 15;
int dp[(1<<15)+1][15];
int f[15];
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<m; j++) {
            int x;
            cin>>x;
            x^=1;
            f[i]|=(x<<j);
        }
    }
    dp[0][0]=1;
    for(int i=1; i<=n; i++) {
        for(int status1=0; status1<(1<<m); status1++) {
            if(status1&(status1<<1)) {
                continue;
            }
            if((status1&f[i])!=0) {
                continue;
            }
            for(int status2=0; status2<(1<<m); status2++) {
                if(status1&status2) {
                    continue;
                }
                dp[status1][i]+=dp[status2][i-1];
                dp[status1][i]%=mod;
            }
        }
    }
    int ans=0;
    for(int status=0; status<(1<<m); status++) {
        ans+=dp[status][n];
        ans%=mod;
    }
    cout<<ans;
    return 0;
}