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