題意：用1*2的瓷磚拼出m*n的矩形。問有多少種拼法。

解法：設(shè)d[i][j]表示第i行狀態(tài)為j的情況下，最多能有多少種拼法，對(duì)于狀態(tài)j，1表示為豎著放置的瓷磚且它橫跨i和i+1兩行，其余皆用0表示。d[i][j] += d[i-1][k]，其中k表示能轉(zhuǎn)移到j(luò)的狀態(tài)。

tag:狀壓dp

1 /* 2 * Author: Plumrain 3 * Created Time: 2013-11-19 01:01 4 * File Name: DP-POJ-2411.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <vector> 10 11 using namespace std; 12 13 #define CLR(x) memset(x, 0, sizeof(x)) 14 #define PB push_back 15 typedef long long int64; 16 17 int n, m; 18 int64 d[20][1<<12]; 19 vector<int> pat[1<<12]; 20 21 bool gao1(int sta) 22 { 23 int x = 0, time = 0; 24 while (sta > 0){ 25 x = sta & 1; 26 sta >>= 1; 27 if (!x){ 28 if (time & 1) return 0; 29 time = 0; 30 } 31 else ++ time; 32 } 33 return !(time & 1); 34 } 35 36 bool gao2(int s1, int s2) 37 { 38 for (int i = 0; i < m; ++ i){ 39 int t1 = s1 & (1<<i), t2 = s2 & (1<<i); 40 if (!t1 && !t2) return 0; 41 42 if (!t1) s2 ^= (1 << i); 43 } 44 return gao1(s2); 45 } 46 47 void init() 48 { 49 for (int i = 0; i < (1<<m); ++ i) 50 pat[i].clear(); 51 for (int i = 0; i < (1<<m); ++ i) 52 for (int j = 0; j < (1<<m); ++ j) 53 if (gao2(j, i)) pat[i].PB(j); 54 } 55 56 int64 DP() 57 { 58 CLR (d); 59 for (int i = 0; i < (1<<m); ++ i) 60 d[0][i] = gao1(i); 61 62 for (int i = 1; i < n; ++ i) 63 for (int j = 0; j < (1<<m); ++ j){ 64 d[i][j] = 0; 65 for (int k = 0; k < (int)pat[j].size(); ++ k) 66 d[i][j] += d[i-1][pat[j][k]]; 67 } 68 69 return d[n-1][(1<<m)-1]; 70 } 71 72 int main() 73 { 74 while (scanf ("%d%d", &n, &m) != EOF && n){ 75 init(); 76 printf ("%lld\n", DP()); 77 } 78 return 0; 79 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/plumrain/p/POJ_2411.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的POJ 2411 Mondriaan's Dream的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。