状态压缩DP总结

状态压缩DP

棋盘类

即对于地图类的问题，当前行只受上一行或者前两行的影响，而不受其他因素的影响，此时可用状态压缩DP
Acwing1064 小国王

• 只受上一行影响

#include <bits/stdc++.h>
using namespace std;
const int N = 12,M = 1 << 10, K = 110;

typedef long long LL;

int n,m;
vector<int> state;
vector<int> head[M];
int cnt[M];
LL f[N][K][M];    //状态表示f[i,j,s]，在前i行摆放了j个国王并且第i行的状态为s

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;

    //求出所有2^n的方案总数，放进state[]中，并计算每种状态中国王（也就是1）的个数
    for (int i = 0;i < 1 << n;++i){
        if (check(i)){
            state.push_back(i);
            cnt[i] = count(i);
        }
    }
    //找出所有符合条件的状态a,b,使得a状态可以转移至b状态
    for (int i = 0;i < (int) state.size();++i){
        for (int j = 0;j < (int) state.size();++j){
            int a = state[i],b = state[j];
            if (!(a & b) && check(a|b))
                head[i].push_back(j);
        }
    }

    //状态转移：f[i,j,a] = f[i-1,j-c,b] c为第a行的国王数目
    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 (auto b : head[a]){
                    int c = cnt[state[a]];
                    if (j >= c){
                        f[i][j][a] += f[i-1][j-c][b];
                    }
                }
            }
        }
    }

    //由于遍历到了n+1，f[n+1][m][0]即为解
    cout << f[n+1][m][0] << endl;
    return 0;
}

大致分三步：首先是枚举1<<m种状态，并且将合法的放入state中保存。这里的合法指的是一行中满足题目要求。第二步每次枚举两个状态，判断这两个状态是否可以转移，即前后两行的状态是否合法，合法便保存在i->j的图中，第三步即状态转移，必须包含的参数有行数和状态数，依据题目条件看是否需要添加其他参数。

• 受上两行的影响
  炮兵阵地

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  typedef unsigned long long uLL;
  typedef pair<int,int> PII;
  typedef pair<LL,LL> PLL;
  #define fi first
  #define se second
  #define mp make_pair
  #define IOS ios::sync_with_stdio(false),cin.tie(0)
  const int N = 11;
  const int M = 1 << 10;
  const int MOD = 998244353;
  const int INF = 0x3f3f3f3f;
  mt19937 mrand(random_device{}()); 
  int rnd(int x) { return mrand() % x;}
  LL powmod(LL a,LL b,LL mod) {LL res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  LL gcd(LL a,LL b) { return b?gcd(b,a%b):a;}
  LL lcm(LL a,LL b) { return a*b/gcd(a,b);}
  int n,m;
  int g[110];
  int cnt[M];
  int f[2][M][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 t;cin >> t;
            if (t == '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 < (int) state.size();++j){
            for (int k = 0;k < (int) state.size();++k){
                for (int u = 0;u < (int) state.size();++u){
                    int a = state[j], b = state[k], c =state[u];
                    if ((a & b) | (a & c) | (b & c))    continue;
                    if ((g[i-1] & a) | (g[i] & b))    continue;
                    f[i & 1][j][k] = max(f[i & 1][j][k],f[(i-1) & 1][u][j] + cnt[b]);
                }
            }
        }
    }
    cout << f[(n+2) & 1][0][0] << endl;
    return 0;
  }

  这里和只受一行的影响差异主要表现在转移方程的形式不同。预处理的大致思路一致，只是要多判断一行即可。

集合类

此类适用于重复覆盖问题和精确覆盖问题
NOIP2016 愤怒的小鸟

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double,double> PDD;
#define fi first
#define se second
#define mp make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(0)
const int N = 18;
const int M = 1 << 18;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
mt19937 mrand(random_device{}()); 
int rnd(int x) { return mrand() % x;}
LL powmod(LL a,LL b,LL mod) {LL res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
LL gcd(LL a,LL b) { return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b) { return a*b/gcd(a,b);}
int n,m;
PDD a[N];
int path[N][N];
int f[M];

int cmp(double x,double y){
    if (fabs(x - y) < eps)    return 0;
    if (x < y)    return -1;
    else return 1;
}
int main(){
    int T;cin >> T;
    while (T--){
        cin >> n >> m;
        for (int i = 0;i < n;++i)    cin >> a[i].fi >> a[i].se;

        memset(path,0,sizeof path);
                //经过(i,j)的抛物线所经过的点
                //求path[i][j]
        for (int i = 0;i < n;++i){
            path[i][i] = 1 << i;
            for (int j = 0;j < n;++j){
                double x1 = a[i].fi,y1 = a[i].se;
                double x2 = a[j].fi,y2 = a[j].se;
                if (!cmp(x1,x2))    continue;
                double aa = (y1 / x1 - y2 / x2) / (x1 - x2);
                double bb = y1 / x1 - aa * x1;
                if (aa >= 0)    continue;
                int state = 0;
                for (int k = 0;k < n;++k){
                    double x = a[k].fi,y = a[k].se;
                    if (!cmp(aa*x*x + bb * x,y))
                        state += 1 << k;
                }
                path[i][j] = state;
            }
        }
        memset(f,0x3f,sizeof f);
        f[0] = 0;
                //枚举所有状态，每次取未被覆盖的点，求可以覆盖此点的抛物线，并更新状态
        for (int i = 0;i + 1 < 1 << n;++i){
            int x = 0;
            for (int j = 0;j < n;++j)
                if (!(i >> j & 1)){
                    x = j;
                    break;
                }
            for (int j = 0;j < n;++j)
                f[i | path[x][j]] = min(f[i | path[x][j]],f[i] + 1);
        }
        cout << f[(1 << n) - 1] << endl;
    }
    return 0;
}