用状态压缩DP的时候往往会用到二进制的枚举以及按位与、按位或的技巧。
1.关于a&b，通过二进制的转换，如果两个数相同位数上的数字相同的话则为1反之为0
2.关于a|b,则和&相反，如果两个数相同位数上的数字有一个是1，那么就为1反之为0
利用这两个技巧我们可以来判断状态是否合法
技巧2：而且为了枚举答案的方便，我们一般在第一层循环的时候多循环一次，这样可以直接输出答案
AcWing 1064. 小国王

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 12,M = 1 << N;

long long  f[N][N*N][M];
int n,m,cnt[M];
vector<int> state;
//存的是符合情况的那些状态
vector<int> head[M];
//head[a][b]:表示的是状态a的符合要求的状态是b（不过在这里我们存储的是state[]里的下标）

bool check(int state)
{
    for(int i=0;i<n;i++)
        if((state >> i & 1)&&(state >> i+1 &1))
        return false;
    return true;
}

int count(int state)
{
    int res=0;
    for(int i=0;i<n;i++)res+=state>>i&1;
    return res;
}

int main()
{
    cin >> n >> m;
    for(int i=0;i<1<<n;i++)
        if(check(i))
        {
            state.push_back(i);
            cnt[i]=count(i);
        }

    for(int i=0;i<state.size();i++)
        for(int j=0;j<state.size();j++)
        {
            int a=state[i],b=state[j];
            if((a&b)==0&&(check(a|b)))
            head[i].push_back(j);
        }

    f[0][0][0]=1;
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<=m;j++)
            for(int a=0;a<state.size();a++)
                for(int b:head[a])
                {
                    int c=cnt[state[a]];
                    if(j>=c)f[i][j][a]=(f[i][j][a]+f[i-1][j-c][b]);
                }
    cout << f[n+1][m][0] << endl;
    return 0;
}

AcWing 327. 玉米田

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 14,M = 1 << N,mod=1e8;

int f[N][M];
vector<int> state;
vector<int> head[M];
int n,m;
int g[N],cnt[M];

bool check(int state)
{
    for(int i=0;i<m;i++)
        if((state>>i&1)&&(state>>i+1&1))
        return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
        {
            int x;
            cin >> x;
            g[i]+=!x<<j;
        }

    for(int i=0;i<1<<m;i++)
        if(check(i))
        state.push_back(i);

    for(int i=0;i<state.size();i++)
        for(int j=0;j<state.size();j++)
        {
            int a=state[i],b=state[j];
            if((a&b)==0)
            head[i].push_back(j);
        }

    f[0][0]=1;
    for(int i=1;i<=n+1;i++)
        for(int a=0;a<state.size();a++)
            for(int b:head[a])
            {
                if((state[a]&g[i]))continue;
                f[i][a]=(f[i-1][b]+f[i][a])%mod;
            }
    cout << f[n+1][0] << endl;
    return 0;
}

AcWing 292. 炮兵阵地

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

const int N = 12 ,M = 1 << 10;

int f[2][M][M];
int n,m,g[M];
int cnt[M];
vector<int> state;

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

int count(int state)
{
    int res=0;
    for(int i=0;i<m;i++)res+=state>>i&1;
    return res;
}

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
        {
            char c;
            cin >> c;
            if(c=='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=1;i<=n+2;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++)
                {
                    // i,i-1,i-2
                    int a=state[j],b=state[k],c=state[u];
                    if((a&b)|(a&c)|(b&c))continue;
                    if((g[i]&a|g[i-1]&b))continue;
                    f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][k][u]+cnt[a]);
                }

    cout << f[(n+2)&1][0][0] << endl;
    return 0;
}