[POJ 2411] Mondriaan's Dream【状压DP】
Problem:
Time Limit: 3000MS | Memory Limit: 65536K |
Description

Expert as he was in this material, he saw at a glance that he'll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!

Input
Output
Sample Input
1 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0 0
Sample Output
1 0 1 2 3 5 144 51205
Source
Solution:
比较恶心的状态压缩 DP。
竖放的骨牌两格均标为 1,横放的骨牌左格标为 0,右格标为 1。
将每列的状态压缩,按行转移即可。
能否转移的限制条件其实只有两个,但实现较为复杂:
- 若前一列的某一行为 0,则这是一个横放的骨牌,本列的这一行必须为 1。
- 若前一列的某一行为 1,且本列的这一行也为 1,则这是竖放的骨牌,前一列的下一行和本列的下一行必须均为 1。本行这一条件满足后,直接跳过下一行的检查。
由于限制条件在行数确定之后就已经确定,我们可以建立邻接表存储状态的前驱。
Code: O(22·min{w,h}(w+h)) [972K, 219MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int h, w, S; long long dp[15][2100]; struct Arc{ int np; Arc *nxt; }; struct Prev_Recorder{ Arc *V[2100], E[1000000]; int tope; inline void clear() {tope = 0, memset(V, 0, sizeof(V));} inline void addedge(int u, int v) {E[++tope].np = v, E[tope].nxt = V[u], V[u] = &E[tope];} inline void build(const int &range){ clear(); int S = 1 << range; for(register int r = 0; r < S; r++) for(register int s = 0; s < S; s++){ bool flag = 0; for(register int i = 0; i < range; i++) if((r & 1 << i) == 0){ // If i-th number of previous column is 0 (-) if((s & 1 << i) == 0){ // Then i-th number of current column must be 1 flag = 1; break; } } for(register int i = 0; i < range; i++){ if((r & 1 << i) && (s & 1 << i)){ // If i-th numbers of both previous column and current column are 1 (|) if(i == range - 1 || (r & 1 << i + 1) == 0 || (s & 1 << i + 1) == 0){ // Then (i+1)-th numbers of both must be 1 flag = 1; break; } else i++; // Jump over the next line } } if(!flag) addedge(s, r); } } } prev; int main(){ while(scanf("%d%d", &h, &w) != EOF && h){ if(h & 1 && w & 1){ puts("0"); continue; } if(h > w) swap(h, w); memset(dp, 0, sizeof(dp)); prev.build(h), S = 1 << h; for(register int s = 0; s < S; s++){ bool flag = 0; for(register int i = 0; i < h; i++) if((s & 1 << i)){ if((s & 1 << i + 1) == 0){ flag = 1; break; } else i++; } if(flag) dp[1][s] = 0; else dp[1][s] = 1; } for(register int i = 2; i <= w; i++) for(register int s = 0; s < S; s++) for(register Arc *ne = prev.V[s]; ne; ne = ne->nxt) dp[i][s] += dp[i - 1][ne->np]; printf("%lld\n", dp[w][S - 1]); } return 0; }
发表评论