題意：4*n的木板，用1*2方塊去貼，問一共有多少種方案。

解題思路：這道題是簡單的狀態壓縮，和之前的鋪方塊是一樣的思路，橫著的為全1，如果有空格等著下一行去鋪就置0，那么下一行的這個位置肯定為1，因為要豎著插把上一行的填滿。剩下的就是簡單的狀態轉移了。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 1005; const int bit = 1<<4; int n,dp[maxn][bit];bool check(int s1,int s2) {if((s1 | s2) != bit-1) return false;int cnt = 0;for(int i = 0; i < 4; i++){if((s1 & (1<<i)) && (s2 & (1<<i))) cnt++;else{if(cnt % 2 == 1) return false;cnt = 0;}}if(cnt % 2 == 1) return false;return true; }int main() {int t,cas = 1;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));scanf("%d",&n);for(int i = 0; i < bit; i++)if(check(i,bit-1) == true)dp[1][i] = 1;for(int i = 2; i <= n; i++)for(int j = 0; j < bit; j++) //第i行狀態for(int k = 0; k < bit; k++) //第i-1行狀態if(check(j,k) == true)dp[i][j] += dp[i-1][k];printf("%d %d\n",cas++,dp[n][bit-1]);}return 0; }

總結

以上是生活随笔為你收集整理的poj 3797(状态压缩dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。