轉載自：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; } }新聞熱點
疑難解答
