状态压缩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;
}