热门标签
当前位置: article > 正文
状态压缩DP_dp状态压缩
作者：数据可视化灵魂 | 2024-01-31 14:43:15
赞
踩
dp状态压缩
状压dp：简单来说就是通过，枚举所有的状态，然后用当前的状态不断的更新其他的状态，从而最终得到最终状态的最优值。这个做题的关键就是在我们枚举到当前状态的时候，当前的状态已经到达了最优值。然后用本身的最优值去更新其他的值，感觉很像最短路中松弛操作。状压dp的问题感觉还是比较好判断的，基本上他的n<=20的，因为我们需要枚举2^n中状态，所以太大的枚举不了。
例题1：棋盘内的状态压缩DP
小国王
题意：
1：给定m个国王
2：给定n*n的矩阵
3：每个国王可以攻击到相邻的八个格子的位置
4：求最大的摆放方案数（要求国王间不能相互进攻）
分析：
1：三维状态压缩DP
2：状态表示：dp[i][j][k]，i是表示对前i行进行处理，j表示当前已经安排了j个国王，k表示第i行的状态
3：转移方程：当前的状态可以由dp[i-1][j-c][k]转移过来，这里的c表示第i行的国王的数量，此方程表达的含义：摆放好了i-1行，已经摆放了j-c个棋子，其中c是第i行棋子的数量。我们发现这一行如果上下两个状态可以满足的话就可以转移（具体的转移要求在代码中标明）。
4：我们需要预处理当前行的状态是否满足情况即是否有两个相邻的1，然后还需要预处理上一个状态能否预处理到下一个状态。
下面是AC代码：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> using namespace std; #define int long long const int N=12,M=1<<10,K=110; int n,m; vector<int> state; int cnt[M]; vector<int> head[M]; int f[N][K][M]; bool check(int state)//判断i中是否有相邻的1 { for(int i=0;i<n;i++) { if((state>>i&1)&&(state>>i+1&1)) return false; } return true; } int count(int state)//统计i中1的数量 { int res=0; for(int i=0;i<n;i++) res+=(state>>i&1); return res; } signed 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]; int b=state[j]; if((a&b)==0&&check(a|b))//这里前一个就是相同的列不能全为1，a|b就是在矩阵中看上下合并的话不能有相邻的1。 { head[i].push_back(j);//将可以转移到i的状态的数量的下标存起来 } } } f[0][0][0]=1;//初始化，表示已经摆了0行，摆了0个国王，状态为0 for(int i=1;i<=n+1;i++)//枚举1-n行 { 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]];//最后一行的1的数量 if(j>=c) f[i][j][a]+=f[i-1][j-c][b];//转移方程，注意转移的时候用的是状态号 } } } } cout<<f[n+1][m][0];//注意这里的0表示的是下标，但是state[0]就是0 return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
注：这里用到了一个技巧就是我们可以枚举到i+1行，就不用最终枚举所有n的状态，这里f[n+1][m][0]就是到了n+1行，用了m个国王，最后一行状态为state[0]即0，可以包含所有的答案。还有就是第三维更新的时候用的是状态下表而不是具体的状态，具体的状态可能很大，用的话可能就会爆数组的内存。
例题2：棋盘内的状态压缩DP
玉米田
题意：
1：N*M的玉米地
2：a[i][j]为1表示此块土地肥沃，a[i][j]=0表示此块土地不育
3：每种一个玉米，与其有一个相邻边的格子不能种玉米
4：问种玉米的最多方案数
题解：此题与上一题是很类似的，只不过状态数变少了而已，但是我们依旧是处理所有可能的状态，然后在转移的时候按照一定的条件转移即可，转移过程中如果可转移的上个状态不存在，加上0即可，不会对最终答案造成影响。
下面是AC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N = 14, M = 1 << 12, mod = 1e8; int n, m; int w[N]; vector<int> state; vector<int> head[M]; int f[N][M];//这里存的是状态 bool check(int state) { for(int i=0;i+1<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=1;j<=m;j++) { int x; cin>>x; w[i]=w[i]*2+x;//计算当前的值 } } 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++) if((state[i]&state[j])==0) head[i].push_back(j); f[0][0]=1; for(int i=1;i<=n+1;i++) { for(int j=0;j<state.size();j++) { if((state[j]|w[i])<=w[i])//保证不育的土地不会种树，假设上面的土地的值为110那么如果0上面有1的话或起来的值一定是大于w[i]的。 { for(int b:head[j]) { f[i][j]=(f[i][j]%mod+f[i-1][b]%mod)%mod; } } } } cout<<f[n+1][0]<<endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
我们也可以变形一下求总方案中玉米的最大数量：
此题代码如下：(测了几个样例过了)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define int long long const int N = 14, M = 1 << 12, mod = 1e8; int n, m; int w[N]; vector<int> state; vector<int> head[M]; int f[N][M];//这里存的是状态 int cnt[M]; bool check(int state) { for(int i=0;i+1<m;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<m;i++) res+=state>>i&1; return res; } signed main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int x; cin>>x; w[i]=w[i]*2+x; } } for(int i=0;i<1<<m;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++) if((state[i]&state[j])==0) head[i].push_back(j); for(int i=1;i<=n+1;i++) { for(int j=0;j<state.size();j++) { if((state[j]|w[i])<=w[i]) { for(int b:head[j]) { f[i][j]=max(f[i][j],f[i-1][b]+cnt[state[j]]); //cout<<state[j]<<"-->"<<cnt[state[j]]<<endl; } } } } cout<<f[n+1][0]<<endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
状态压缩dp除了上面说的棋盘类的，还有就是普通的二进制形式。我们下面举几个例题来理解：
例题1：Rectangular Covering
题意：
1：平面上给出n个点（二维坐标）
2：要求用平行于轴的矩形来覆盖这些点
3：问覆盖所有点最小的总面积
注：假设是同一行或同一列的点需要将变化为宽为1的长方形
题解：
这个题的话还是比较简单的，我们按照输入的顺序，将一个点看作一个状态，然后预处理任意两个点的矩形面积和之间的点，求到相应的状态，然后存入一个vector里面最后在将所有的状态状压一下即可，下面是AC代码：
#include <iostream> #include <cstring> #include <cstdio> #include <bitset> #include <vector> using namespace std; const int N = 20; int dp[1 << N]; struct node { int x, y; } a[1 << N]; int main() { int n; while (~scanf("%d", &n) && n) { vector<pair<int, int> > vec(1<<N); for (int i = 0; i < n; i++) { int x, y; scanf("%d%d", &x, &y); a[i].x = x; a[i].y = y; } int cnt = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { bitset<15> bit; int maxx = max(a[i].x, a[j].x); int minx = min(a[i].x, a[j].x); int maxy = max(a[i].y, a[j].y); int miny = min(a[i].y, a[j].y); for (int k = 0; k < n; k++) { if (a[k].x >= minx && a[k].x <= maxx && a[k].y >= miny && a[k].y <= maxy) { bit.set(k, 1); } } int v = 0; for (int k = bit.size() - 1; k >= 0; k--) { v = v * 2 + bit[k]; } if (minx == maxx) vec[cnt].first = v, vec[cnt++].second = maxy - miny; else if (miny == maxy) vec[cnt].first = v, vec[cnt++]. second = maxx - minx; else vec[cnt].first = v, vec[cnt++].second = (maxx - minx) * (maxy - miny); } } for(int i=0;i<(1<<n);i++) dp[i]=0x3f3f3f3f; dp[0] = 0; for (int i = 0; i < (1 << n); i++) { for (int j = 0; j < cnt; j++) { int v1 = i; int v2 = vec[j].first; int num = vec[j].second; int t = v1 | v2; dp[t] = min(dp[t], dp[i] + num); } } printf("%d\n", dp[(1 << n) - 1]); } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
例题2：DNA Laboratory
题意：给出n个字符串，构造求一个最小长度的串，该串包含给出的所有字符串。注意该字符串在长度最小的同时还必须是字典序最小
题解：感觉这个还是有一定的难度的，状压的过程还可以，但是回溯寻找原串的过程比较麻烦。
这个题的本质就是一个状压dp中顺序的问题，感觉这种问题还是比较常见的，我们设置dp[i][j]表示状态为j的情况下， i i i放到最前面的情况。
这样我们的状压方程也就很容易表示了，但是，我们还要预处理一个东西就是，任意一个串放到另一个串的前面给整体的串带来的长度贡献是多少。这两项知道了，方程也就很容易求了。
我们通过上面的东西可以得到的是最小长度，题目还有的要求是要将整个串的字典序最小输出出来，这个通用的做法就是dfs回溯找出，具体的戳我
下面是AC代码：
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <bitset> using namespace std; const int N = 20; const int INF = 0x3f3f3f3f; //思路:先求最小长度,然后再dfs回滚求字典序最小 int dp[20][(1 << 20)]; // dp[i][j]表示状态j,第i个字符串放在最前面的最小长度 int cost[20][20]; // cost[i][j]表示第i个字符串放到第j个字符串前的花费长度 string s[20], ans; int m; void dfs(int id, int cur) //从id开始，cur为当前的状态 { if (cur == 0) return; int flag = -1; string tmp = "zzzz"; for (int i = 0; i < m; i++) //从前往后枚举字符串 { if (i == id) continue; if ((cur & (1 << i)) && (dp[id][cur] == dp[i][cur & ~(1 << id)] + cost[id][i])) { if (s[i].substr(s[id].size() - cost[id][i]) < tmp) { tmp = s[i].substr(s[id].size() - cost[id][i]); flag = i; } } } if (flag != -1) ans += tmp; dfs(flag, cur & ~(1 << id)); } int main() { int t; scanf("%d", &t); int Case=0; while (t--) { ans=""; int n; scanf("%d", &n); for (int i = 0; i < n; i++) cin >> s[i]; //去重 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (s[i].find(s[j]) != -1) s[j] = s[i]; cost[i][i]=0; } } sort(s, s + n); //从小到大 m = unique(s, s + n) - s; memset(cost, 0, sizeof(cost)); //找到cost[i][j]//第i个字符串放在最前面的最小长度 for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { if (i == j) continue; int len = min(s[i].size(), s[j].size()); int mx = 0; //最大的相同长度 for (int k = s[i].size() - len; k < s[i].size(); k++) { string s1 = s[i].substr(k); //从i开始到最后的子串 int midl = s1.size(); string s2 = s[j].substr(0, midl); if (s1 == s2) { mx = max(mx, midl); } } cost[i][j] = s[i].size() - mx; } } //进行状压dp for (int i = 0; i < m; i++) { for (int j = 0; j < (1 << m); j++) dp[i][j] = 0x3f3f3f3f; } for (int i = 0; i < m; i++) { dp[i][(1 << i)] = s[i].size(); } for (int i = 0; i < (1 << m); i++) { for (int j = 0; j < m; j++) { if ((i & (1 << j)) && dp[j][i] != INF) { for (int k = 0; k < m; k++) { dp[k][i | (1 << k)] = min(dp[k][i | (1 << k)], dp[j][i] + cost[k][j]); //用当前的状态去更新其他的状态 } } } } int id = 0; for (int i = 0; i < m; i++) { if (dp[id][(1 << m) - 1] > dp[i][(1 << m) - 1]) { id = i; } } ans += s[id]; dfs(id, (1 << m) - 1); cout<<"Scenario #"<<++Case<<":"<<endl; cout << ans << endl<<endl;//记得多加一个endl，否则会PE } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
例题3：Paid Roads
题意：
题解：这个题的主要的问题就是那个可以提前支付的问题，也就是说这个题的最小值可能是重复走一些边才会得到。
所以，我们要暴力所有的状态，判断当前的状态的相应位置是不是1，假设是1的话就更新与他相连的所有位置，但是这个更新的时候类似于dijistra更新，只要是有状态更新了，就一直更新，只要没状态更新，就跳出。大致除了用了dijistra的思想外，其余基本和模板类似，具体看代码：
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<queue> using namespace std; #define int long long const int inf=0x3f3f3f3f; int dp[1<<11][11];//dp[i][j]表示在i的状态下，最后一个遍历到j所可以的最小值 struct node { int b,c,p,r;//分别表示目的城市，提前付费的城市，付费多少，不提前付费付多少 }; vector<node> ma[20]; signed main() { int n,m; scanf("%lld%lld",&n,&m); while(m--) { int a,b,c,p,r; node t; scanf("%lld%lld%lld%lld%lld",&a,&t.b,&t.c,&t.p,&t.r); a--; t.b--; t.c--; ma[a].push_back(t); } for(int i=0;i<(1<<n);i++) { for(int j=0;j<n;j++) { dp[i][j]=0x3f3f3f3f; } } dp[1][0]=0; for(int i=0;i<(1<<n);i++) { int flag=1; while(flag)//松弛操作，假设有可以更新的就更新 { flag=0; for(int j=0;j<n;j++) { if(!(i&1<<j)) continue; for(int k=0;k<ma[j].size();k++) { int tmp=inf; int v=ma[j][k].b; if(i&1<<ma[j][k].c) tmp=min(tmp,dp[i][j]+ma[j][k].p); tmp=min(tmp,dp[i][j]+ma[j][k].r); if(tmp<dp[i|1<<v][v]) { dp[i|1<<v][v]=tmp; flag=1; } } } } } int ans=inf; for(int i=0;i<(1<<n);i++) { if(i&1) ans=min(ans,dp[i][n-1]);//是奇数，因为必须要有1 } if(ans==inf) printf("impossible\n"); else printf("%lld\n",ans); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
持续更新中~~~~~~~~
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/50841
推荐阅读
相关标签
