首页 > 代码库 > 状态压缩动态规划总结
状态压缩动态规划总结
状态压缩是一个很广的概念，在OI中也有很多的应用，当我们把他应用到动态规划中，可以用来精简状态，节约空间，也方便转移。最常见的就是用二进制来表是状态，利用各种位移运算，就可以实现\(O(1)\)的转移。状压DP适用于“窄棋盘”上的DP，否则状态太多无法存下。
POJ1185 炮兵阵地
题意：给一个\(N \times M\)的地形盘，有平原和山坡，要求在平原上部署尽量多的炮（攻击范围2），使得不互相攻击。
数据范围：N <= 100；M <= 10，符合条件。如何表示状态？按行DP，一个二进制数（m<=10，int足够了，最大状态数：(1 << 10) = 1024，但有很多不合法状态）上的某位等于1表示在此处有炮。用F[i][j][k]表示在i行，当前行状态为j，前一列状态为k时的最优解。二进制的优势在此时体现出来了：我可以\(O(1)\)判断状态是否合法，详见代码，此处需要深入体会。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 60 + 10; 7 8 int G[maxn*2],State[maxn],Num[maxn*2],dp[maxn*2][maxn][maxn]; 9 10 int main()11 {12 int n,m;13 int Snum=0;14 15 scanf("%d%d\n",&n,&m);16 for(int i=0;i<n;++i)17 {18 for(int j=0;j<m;++j)19 {20 char c=getchar();21 if(c==‘H‘)22 G[i]+=1<<j;23 }24 getchar();25 }26 27 for(int i=0;i<(1<<m);++i)28 {29 if((i&(i<<1)) || (i&(i<<2)))30 continue;31 int k=i;32 while(k)33 {34 Num[Snum]+=k&1;35 k>>=1;36 }37 State[Snum++]=i;38 }39 40 for(int i=0;i<Snum;++i)41 {42 if(State[i]&G[0])43 continue;44 dp[0][i][0]=Num[i];45 }46 47 for(int i=0;i<Snum;++i)48 {49 if(State[i]&G[1])50 continue;51 for(int j=0;j<Snum;++j)52 {53 if((State[i]&State[j]) || (State[j]&G[0]))54 continue;55 dp[1][i][j]=max(dp[1][i][j],dp[0][j][0]+Num[i]);56 }57 }58 59 for(int i=2;i<n;++i)60 {61 for(int j=0;j<Snum;++j)62 {63 if(State[j]&G[i])64 continue;65 for(int k=0;k<Snum;++k)66 {67 if(State[k]&State[j])68 continue;69 if(State[k]&G[i-1])70 continue;71 for(int p=0;p<Snum;++p)72 {73 if(State[p]&G[i-2])74 continue;75 if(State[p]&State[k])76 continue;77 if(State[p]&State[j])78 continue;79 dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][p]+Num[j]);80 }81 }82 }83 }84 85 int ans=0;86 for(int i=0;i<Snum;++i)87 for(int j=0;j<Snum;++j)88 ans=max(ans,dp[n-1][i][j]);89 printf("%d\n",ans);90 return 0;91 }
POJ3254 Corn Fields
题意：一个row*col的矩阵，每个格子是0或者1，1表示土壤肥沃可以种植草地，0则不可以。在种草地的格子可以放牛，但边相邻的两个格子不允许同时放牛，问总共有多少种放牛的方法？（不放牛也算一种情况）
数据范围：1 ≤ M ≤ 12; 1 ≤ N ≤ 12，同样的小棋盘模型。做法其实都差不多，关键是状态的转移，这道题比上一道题要容易些。
1 #include <cstdio> 2 #include <cstring> 3 const int maxn = 15; 4 const int maxs = 5000; 5 const int Mod = 1e8; 6 7 int State[maxs],Snum; 8 int G[maxn]; 9 int dp[maxn][maxs];10 int n,m;11 12 void init()13 {14 for(int i=0;i<(1<<m);++i)15 if(!(i&(i<<1)))16 State[Snum++]=i;17 }18 19 int main()20 {21 freopen("data.out","w",stdout);22 freopen("data.in","r",stdin);23 24 scanf("%d%d",&n,&m);25 for(int i=0;i<n;++i)26 for(int j=0;j<m;++j)27 {28 int t;29 scanf("%d",&t);30 if(t==0)31 G[i]+=(1<<j);32 }33 init();34 35 for(int i=0;i<Snum;++i)36 if(!(State[i]&G[0]))37 dp[0][i]=1;38 39 for(int i=1;i<n;++i)40 for(int j=0;j<Snum;++j)41 {42 if((State[j]&G[i]))43 continue;44 for(int k=0;k<Snum;++k)45 {46 if((State[k]&G[i-1]) || (State[k]&State[j]))47 continue;48 dp[i][j]=(dp[i][j]+dp[i-1][k])%Mod;49 }50 }51 int ans=0;52 for(int i=0;i<Snum;++i)53 ans=(ans+dp[n-1][i])%Mod;54 printf("%d\n",ans);55 return 0;56 }
BZOJ1087: [SCOI2005]互不侵犯King
题意：在N×N的棋盘里面放K个国王，使他们互不攻击，求共有多少种摆放方案。
数据范围：1 <=N <=9, 0 <= K <= N * N，好小的N。。。国王的攻击范围是什么？想清楚了就是sb题了。
贴一个以前写的题解：
当前状态只会影响下一行的状态。用f[i][j][k]表示行i处状态为j时使用k个棋子可行的方案数。判状态转移时，两个状态S1与S2融洽的条件是!((S1<<1)&S2) && !((S1>>1)&S2) && !(S1&S2)，且S1本身可行的条件是：!((S1<<1)&S1) && !((S1>>1)&s1)。
位运算真是个好东西。。
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxn = 512 + 20; 5 6 typedef long long LL; 7 8 LL f[10][maxn][maxn]; 9 bool ok[10][maxn];10 int main()11 {12 13 int n,m;14 scanf("%d%d",&n,&m);15 16 memset(f,0,sizeof f);17 memset(ok,false,sizeof ok);18 19 f[0][0][0]=1;20 ok[0][0]=true;21 for(int i=1;i<=n;++i)22 {23 for(int j=0;j<(1<<n);++j)24 {25 if(ok[i-1][j])26 {27 for(int k=0;k<(1<<n);++k)28 {29 if(((k<<1)&k) || ((k>>1)&k)) continue;30 if((j&k) || ((j<<1)&k) || ((j>>1)&k)) continue;31 int tmp=k,cnt=0;32 while(tmp)33 {34 if(tmp&1)35 ++cnt;36 tmp>>=1;37 }38 ok[i][k]=true;39 for(int p=0;p+cnt<=m;++p)40 f[i][k][p+cnt]+=f[i-1][j][p];41 }42 }43 }44 }45 46 LL ans=0;47 for(int j=0;j<(1<<n);++j)48 ans+=f[n][j][m];49 printf("%lld\n",ans);50 return 0;51 }
看了3道棋盘规划型的题，我们来看一些棋盘覆盖的例子。
POJ2411 Mondriaan‘s Dream
题意：一个h*w的矩阵，希望用2*1或者1*2的矩形来填充满，求填充的总方案数。
数据范围：1<=h,w<=11。这道题是非常经典的棋盘覆盖状压DP。讲一个优化：先将可以兼容的状态dfs出来。详见代码。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 using namespace std; 6 7 const int maxn = 14; 8 const int maxs = 40000; 9 typedef unsigned long long UI;10 11 int n,m;12 vector<int> State[maxs];13 int Snum;14 UI dp[maxn][maxs];15 16 void dfs(int col,int S1,int S2)17 {18 if(col>=m)19 {20 if(S1<(1<<m) && S2<(1<<m))21 State[S2].push_back(S1);22 return;23 }24 dfs(col+1,(S1<<1)|1,S2<<1);25 dfs(col+1,S1<<1,(S2<<1)|1);26 dfs(col+2,(S1<<2)|3,(S2<<2)|3);27 }28 29 void solve()30 {31 Snum=1<<m;32 memset(dp,0,sizeof dp);33 for(int i=0;i<Snum;++i)34 State[i].clear();35 dfs(0,0,0);36 dp[0][0]=1;37 for(int i=1;i<=n+1;++i)38 for(int j=0;j<Snum;++j)39 for(int k=0,sz=State[j].size();k<sz;++k)40 dp[i][j]+=dp[i-1][State[j][k]];41 printf("%lld\n",dp[n+1][Snum-1]);42 }43 44 int main()45 {46 while(scanf("%d%d",&n,&m)!=EOF && n!=0 && m!=0)47 {48 if((n&1) && (m&1))49 {50 puts("0");51 continue;52 }53 if(n<m)54 swap(n,m);55 solve();56 }57 return 0;58 }
SGU131 Hardwood floor
题意：在\(N \times M\)的棋盘内放1*2及2*2去掉一个角的块，问方案数。
数据范围：1<=M<=9, 1<=N<=9。原理是一样的，同样可以dfs出兼容的状态。但是具体如何实现还是有问题的，因为第二种块太奇葩了（第二种块：我tm哪里奇葩啦！）。dfs多传入两个参数：f1, f2，代表上一列摆放块对当前的影响。
1 #include <string> 2 #include <bitset> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 using namespace std; 8 9 const int maxn = 11;10 const int maxs = 1000;11 12 typedef long long LL;13 14 LL dp[maxn][maxs];15 vector<int> State[maxs];16 int n,m,Snum;17 18 bitset<13> tmp;19 void dfs(int col, int s1, int s2, int f1, int f2) {20 if(m <= col) {21 if(!f1 && !f2) {22 /*23 tmp = s1;24 printf("%s ", tmp.to_string().c_str());25 tmp = s2;26 printf("%s ", tmp.to_string().c_str());27 tmp = s2 ^ (Snum - 1);28 printf("%s\n", tmp.to_string().c_str());29 */30 State[s2 ^ (Snum - 1)].push_back(s1);31 }32 return ;33 }34 dfs(col + 1, (s1 << 1) + f1, (s2 << 1) + f2, 0, 0);35 // 可以尝试把上面那句话去掉36 // 。。。然后你就只能得到一种状态：放满了的。。37 if(!f1) {38 if(!f2) {39 dfs(col + 1, (s1 << 1) + 1, (s2 << 1) + 1, 0, 0);40 dfs(col + 1, (s1 << 1) + 1, (s2 << 1) + 1, 1, 0);41 dfs(col + 1, (s1 << 1) + 1, (s2 << 1) + 1, 0, 1);42 }43 dfs(col + 1, (s1 << 1) + 1, (s2 << 1) + f2, 1, 0);44 dfs(col + 1, (s1 << 1) + 1, (s2 << 1) + f2, 1, 1);45 }46 if(!f2) {47 dfs(col + 1, (s1 << 1) + f1, (s2 << 1) + 1, 1, 1);48 }49 }50 51 LL solve() {52 dp[0][Snum-1]=1;53 for(int i=1;i<=n;++i)54 for(int j=0;j<Snum;++j)55 for(int k=0,sz=State[j].size();k<sz;++k)56 dp[i][j]+=dp[i-1][State[j][k]];57 return dp[n][Snum-1];58 }59 60 int main() {61 scanf("%d%d",&n,&m);62 if(n<m)63 swap(n,m);64 Snum=1<<m;65 dfs(0, 0, 0, 0, 0);66 printf("%lld\n",solve());67 return 0;68 }
SGU132 Another Chocolate Manic
详见此处：http://www.cnblogs.com/hzf-sbit/p/3870652.html
OK，以上就是本人最近（呵呵）做的几道状态压缩DP题。
然后状态压缩还有个很好玩的东东：基于联通性的状态压缩动态规划，俗称：插头DP，以后再总结。。。
PS：欢迎指教~~
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。