hdu1400/acwing 291 Mondriaan's Dream
題意描述:
給定一塊n*m的區域,用1*2的長方形填充,長方形可以橫著或豎著擺,問一共有多少種填充方案
具體思路:
題意沒什么好說的,簡單易懂,很經典的一類狀態壓縮問題(在棋盤中求填充方案)。
觀察數據,滿足n,m都比較小,但是搜索的復雜度大到無法接受,考慮使用狀態壓縮求解此類問題
首先,肯定是第一步,即對題目給定的圖進行初始化,初始化應該怎么搞?觀察到若使用橫著填的方法填充一行的情況,發現有很多單行中有奇數數量的橫向填充方案完全不合法,考慮初始化。即預處理出合理的情況,用桶來記錄,稍后再篩選出合法的情況。
第一步篩選完成了,雖然排除了許多冗余的情況,但是如此大的數據直接dp,兩個指數級別的數相乘會導致復雜度完全無法接受,所以考慮第二步初始化,即將本行的狀況與上一行進行比對,確定最終到底有幾個合法的情況。
最后一步進入正題,dp環節,dp環節和為什么這樣轉移在代碼中解釋
代碼實現:
#include<bits/stdc++.h> using namespace std; const int N=1<<13; long long dp[13][N],n,m; bool st[N];//桶數組判斷合法狀態 vector<vector<long long> >G(N);//第二步篩選后的合法狀態 int main() { while(cin>>n>>m,n||m) { for(int i=0;i<(1<<n);i++) { int cnt=0;bool isvalid=true;//記錄當前有幾個0 for(int j=0;j<n;j++) { if((i>>j)&1)//取出當前為的值,如果當前位為一,之前的cnt記錄的"0"的個數清空,接著判斷當前狀態是否合法 { if(cnt&1)//如果cnt為偶數,不合法 { isvalid=false; break; } cnt=0;//清空不清空差不多 } else cnt++;//當前位為“0”,繼續累加 } if(cnt&1) isvalid=false;//判斷最后一行是什么情況 st[i]=isvalid; } for(int j=0;j<(1<<n);j++) { G[j].clear();//初始化 for(int k=0;k<(1<<n);k++) {
//細說st[j|k],關鍵至極
//首先,j&k是判斷是否是上一行是"1",下一行是"0",因為不是這樣就不合法,簡言之,只要j&k==1就不合法
//再就是st[j|k]
//首先要了解一點,就是k枚舉的是上一行的所有狀態,所以st[j|k]是什么意思呢
//明確,st存的是所有合法的狀態,如果j|k它不是一個合法的狀態,即此時會有奇數個零,那么實際上這個狀態它是不合法的,即上一行伸長下來和這一行伸長下去的,這些被伸長或者伸長下去的
//是不能供橫著放的格子放的
//所以要這樣 if((j&k)==0&&st[j|k]) { G[j].push_back(k); } } } memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=m;i++) { for(int j=0;j<(1<<n);j++) { for(auto k:G[j]) { dp[i][j]+=dp[i-1][k];//當前行的狀態的答案是上一行所有可能情況的和 } } } cout<<dp[m][0]<<endl;//答案就是已經填到m行,且當前行沒有向下伸長的情況 } return 0; }

浙公網安備 33010602011771號