转载自：http://blog.csdn.net/math_coder/article/details/9671581
如果看不明白代码的位运算，请先了解下位运算的应用
---------------------------------------------------------------------------------------------------------------------------
**********此文章属于原创，看此文章前请先参考论文 周伟《动态规划之状态压缩》**********
问题1：
在n*n(n≤20)的方格棋盘上放置n个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。
如果用组合学的角度来考虑此问题，那么非常简单：
我们一行一行放置，第一行有n种选择，第二行n-1，……，最后一行有1种选择，根据乘法原理，答案就是n!
这里我们介绍另一种解法：状态压缩递推(States ComPRessing Recursion,SCR)。
我们仍然一行一行放置。取棋子的放置情况作为状态，某一列如果已经放置棋子则为1，否则为0。这样，一个状态就可以用一个最多20位的二进制数表示。例如n=5,第1、3、4列已经放置，则这个状态可以表示为01101(从右到左)。设fs为达到状态s的方案数，则可以尝试建立f的递推关系。考虑n=5,s=01101因为我们是一行一行放置的，所以当达到s时已经放到了第三行。又因为一行能且仅能放置一个车，所以我们知道状态s一定来自：①前两行在第3、4列放置了棋子(不考虑顺序，下同)，第三行在第1列放置；
②前两行在第1、4列放置了棋子，第三行在第3列放置；
③前两行在第1、3列放置了棋子，第三行在第4列放置。
这三种情况互不相交，且只可能有这三种情况，根据加法原理，fs应该等于这三种情况的和。写成递推式就 是：
f(01101) = f(01100) + f(01001) ＋ f(00101);
根据上面的讨论思路推广之，得到引例的解决办法：f(0) = 1;
f(s) = ·f(s-2^i);
其中s的右起第i+1位为1(其实就是在枚举s的二进制表示中的1)
代码如下：
[cpp] view plain copy print?#include<iostream> #include<cstdio> using namespace std; long long f[1<<20]; int main(){ long long n; while(cin>>n){ memset(f,0,sizeof(f)); f[0] = 1; long long i,t; for( i=1; i< 1<<n; i++){ for( t=i; t>0; t -= (t & -t)){ f[i] += f[i & ~(t & -t)]; //注意理解 } } cout<<f[(1<<n)-1]<<endl; } }
问题2：在n*n(n≤20)的方格棋盘上放置n 个车，某些格子不能放，求使它们不能互 相攻击的方案总数。输入：给你一个n和m，分别表示棋盘的大小，不能放的格子总数 接下来是m行坐标，表示不能放置的位子。输出：符合条件的方案总数。
0表示可以放置，1表示不能放置0 1 00 0 10 0 0输入：3 2 1 2 2 3 输出：3输入：4 11 1 输出：3*3*2*1 == 18提示：1 0 0 00 0 0 00 0 0 00 0 0 0
[cpp] view plain copy print?#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long f[1<<20]; long long vist[22]; int main(){ long long n,m; while(cin>>n>>m){ memset(f,0,sizeof(f)); memset(vist,0,sizeof(vist)); for(int i=0;i<m;i++){ int a,b; cin>>a>>b; vist[a] += 1<<(b-1); //某一个位置不能放置，把这个位置压缩成整数 } f[0] = 1; for(int i=1;i< 1<<n; i++){ int num = 0; for(int j=i;j>0;j -= (j & -j)) num++; //计算 i 这一个状态 1 的个数，也就是最多包涵的行数 for(int j=i;j>0;j -= (j & -j)) { if(!(vist[num]&(j & -j))) f[i] += f[ i& ~(j & -j)];//判断该位置是否可以放置 } } cout<<f[(1<<n)-1]<<endl; } }问题3：给出一个n*m 的棋盘(n、m≤80,n*m≤80)，要在棋盘上放k(k≤20)个棋子，使得任意两个棋子不相邻。求可以放置的总的方案数
[cpp] view plain copy print?#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int s[1<<10],c[1<<10],f[82][1<<9][21]; int n,m,num,flag,val; void DFS(int ans,int pos,int flag){ /////////////////////// if(pos>n) { s[++num] = ans; c[num] = flag; return; } DFS(ans,pos+1,flag); DFS(ans+(1<<pos-1),pos+2,flag+1); } int main(){ while(cin>>n>>m>>val){ if(n>m) swap(n,m); // 行列交换 num = 0; // 状态数初始化 DFS(0,1,0); // 参数：当前状态，位置，1的个数 ，找出一行中符合条件的总数 memset(f,0,sizeof(f)); /////////////////////////////////////////// for(int i=1;i<=num;i++) //第一行进行初始化，状态中有多少个1就初始多少 f[1][s[i]][c[i]] = 1; for(int i=2;i<=m;i++){ //第几行 for(int j=1;j<=num;j++){ //某一行的某个状态 for(int r=1;r<=num;r++){ //上一行的某个状态 if(!(s[j]&s[r])){ //当前行和上一行状态不冲突 for(int k=0;k<=val;k++){ //枚举当前一行棋子的个数 if(k>=c[j]) f[i][s[j]][k] += f[i-1][s[r]][k-c[j]]; //借助上一行的状态枚举当前状态 } } } } } long long sum=0; for(int i=1;i<=num;i++) // 累加最后一行符合条件的总数 sum += f[m][s[i]][val]; cout<<sum<<endl; } } /* 由于数据缺乏，自己模拟了几组数据 输入：3 3 2 输出：23 输入： 2 2 2 输出： 2 输入：20 1 2 输出： 171 */
问题4： 在n*n(n≤10)的棋盘上放k 个国王(可攻击相邻的8 个格子)，求使它们无法互相攻击的方案数。
[cpp] view plain copy print?#include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; long long f[11][1<<10][30]; int s[1<<10],c[1<<10],num; int n,m,val; void DFS(int ans,int pos,int flag){ if(pos>n){ s[++num] = ans; c[num] = flag; return ; } DFS(ans,pos+1,flag); DFS(ans+(1<<pos-1),pos+2,flag+1); } int main(){ while(cin>>n>>m>>val){ num = 0; DFS(0,1,0); memset(f,0,sizeof(f)); for(int i=1;i<=num;i++) f[1][s[i]][c[i]]=1; for(int i=2;i<=n;i++){ for(int j=1;j<=num;j++){ //当前行 for(int r=1;r<=num;r++){ //上一行 if((s[j]&s[r]) || ((s[j]>>1)&s[r]) || ((s[j]<<1)&s[r])) continue; //八个方向判断 for(int k=0;k<=val;k++){ if(k>=c[j]) f[i][s[j]][k] += f[i-1][s[r]][k-c[j]]; } } } } long long sum=0; for(int i=1;i<=num;i++) sum += f[n][s[i]][val]; cout<<sum<<endl; } } /* 输入：3 3 2 输出：16 输入：2 2 1 输出：4 输入：3 3 3 输出：8 输入：9 9 2 输出：1968 */ 题目5：给出一个n*m(n≤100,m≤10)的棋盘，一些格子不能放置棋子。求最多能在
棋盘上放置多少个棋子，使得每一行每一列的任两个棋子间至少有两个空格。
[cpp] view plain copy print?#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; long long f[11][1<<10]; int n,m,s[1<<10],c[1<<10]; int num,ant,a[1<<10]; void DFS(int ans,int pos,int flag){ if(pos>m){ s[++num] = ans; c[num] = flag; return ; } DFS(ans,pos+1,flag); DFS(ans+(1<<pos-1),pos+3,flag+1); } int main(){ while(cin>>n>>m>>ant){ int p,q; for(int i=0;i<ant;i++){ cin>>p>>q; a[p] += (1<<q-1); } memset(f,0,sizeof(f)); num = 0; DFS(0,1,0); // for(int i=1;i<=num;i++) cout<<s[i]<<" "<<c[i]<<endl; for(int i=1;i<3 && i<=n;i++){ for(int j=1;j<=num;j++){ // i==2时，表示当前行 , i==1时表示当前行 if(i==1){ if(a[i]&s[j]) continue; // 不能放置 f[i][s[j]]=c[j]; } else { if(a[i]&s[j]) continue; // 不能放置 for(int r=1;r<=num;r++){ // 不能放置并且和状态 1 不冲突 , 表示前一行的状态 if(a[i-1]&s[r]) continue; // 不能放置 if((s[j]&s[r])) continue; f[i][s[j]] = max(f[i][s[j]],f[i-1][s[r]]+c[j]); } } } } for(int i=3;i<=n;i++){ for(int j=1;j<=num;j++){//当前行 if(s[j]&a[i]) continue; for(int r=1;r<=num;r++){//上一行 i-1 if((s[r]&a[i-1]) || (s[j]&s[r])) continue; for(int h=1;h<=num;h++){//再上一行 i-2 if((s[h]&a[i-3])||(s[j]&s[h])||(s[r]&s[h])) continue; f[i][s[j]] = max(f[i][s[j]],f[i-2][s[h]]+c[j]+c[r]); } } } } long long sum = 0; for(int i=1;i<=num;i++) sum = max(f[n][s[i]],sum); cout<<sum<<endl; } } /* 输入： 3 3 3 2 1 2 2 2 3 输出：2 */题目6: 给出n*m(1≤n、m≤11)的方格棋盘，用1*2 的长方形骨牌不重叠地覆盖这个棋盘，求覆盖满的方案数。
[cpp] view plain copy print?#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<string> using namespace std; long long f[12][1<<14]; int s1[1<<14],s2[1<<14],s[1<<14],ss[1<<14]; int n,m,num,flag; bool vist[1<<14]; void DFS(int ans1,int ans2,int pos){ if(pos>n) { if(pos==n+1) { s1[++num] = ans1; s2[num] = ans2; } return ; } DFS(ans1,ans2,pos+1); // 不放 DFS(ans1+(1<<pos-1)+(1<<pos),ans2,pos+2); // 横放 DFS(ans1+(1<<pos-1),ans2+(1<<pos-1),pos+1); // 竖放 } void dfs(int ans,int pos){ if(pos>n){ if(pos==n+1) s[++flag] = ans; return; } dfs(ans,pos+1); dfs(ans+(1<<pos-1)+(1<<pos),pos+2); } int main(){ while(cin>>n>>m){ if(n==0 && m==0) break; if(n%2 && m%2){ cout<<'0'<<endl; continue; } if(n > m) swap(n,m); if(n%2) swap(n,m); if(m==1) { cout<<'1'<<endl; continue; } num = 0; flag = 0; DFS(0,0,1); dfs(0,1); // 第一行所有状态搜索 memset(f,0,sizeof(f)); for(int i=1;i<=flag;i++) f[1][s[i]] = 1; int ant = (1<<n) - 1; for(int i=1;i<=num;i++){ //第二行 ss[i] = s1[i]; for(int j=1;j<=flag;j++){ //第一行 if((s2[i]&s[j])) continue; if((ant-s2[i])&(ant-s[j])) continue; //处理相同的 0 f[2][s1[i]] += f[1][s[j]]; } } sort(ss+1,ss+num); int ans = 0; ss[++ans] = ss[1]; for(int i=2;i<=num;i++){ //除去相同的 ，避免重复计算 if(ss[i]!=ss[i-1]) ss[++ans] = ss[i]; } for(int i=3;i<=m;i++){ //第三行 for(int j=1;j<=num;j++){//第 i 行状态遍历 for(int r=1;r<=ans;r++){ // 第 i-1 行 *****相同的 s1[r]只能计算一次 WA了N久 if(s2[j]&ss[r]) continue; if((ant-s2[j])&(ant-ss[r])) continue; f[i][s1[j]] += f[i-1][ss[r]]; } } } cout<<f[m][(1<<n)-1]<<endl; } }新闻热点
疑难解答
