本文主要是介绍POJ 2411 Mondriaan's Dream 据说超时可以打表^_^)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：Mondriaan's Dream
状态压缩，超时，于是花2分钟打个表<(￣︶￣)>
思路：（虽然超时。。。）
0 表示没有覆盖
1 表示已经覆盖
dp[i][s] 表示第 i 行使用状态 s 的方案数
dp[i][s] = ∑dp[i-1][ss] ss 为 枚举的第 i-1行的情况
注意：
1. ss 中的0表示没有覆盖 ，需要第 i 行在此处放一块 竖着的砖
所以 s 和 ss 不能在相同的位置同时为 0
即当 ss 在某处是 0的话 s在该处必须是 1 且只能竖着放
2. ss 中的1表示已经覆盖 ，故第 i 行在此处可以选择放（1）一块横着的砖或者不放（0）
如果放横着的砖，需要两个连续的1，同时上一行也要有2个连续的1
比如 ss 是 010 的时候，s 取任意值都是不合理的
PS : 1*2 的小矩形拼出来的面积必然为偶数
若 h*w 为奇数 puts("0")
AC代码：
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
/*0 表示没有覆盖1 表示已经覆盖dp[i][s] 表示第 i 行使用状态 s 的方案数dp[i][s] = ∑dp[i-1][ss] ss 为 枚举的第 i-1行的情况注意：1. ss 中的0表示没有覆盖 ，需要第 i 行在此处放一块 竖着的砖所以 s 和 ss 不能在相同的位置同时为 0即当 ss 在某处是 0的话 s在该处必须是 1 且只能竖着放2. ss 中的1表示已经覆盖 ，故第 i 行在此处可以选择放（1）一块横着的砖或者不放（0）如果放横着的砖，需要两个连续的1，同时上一行也要有2个连续的1比如 ss 是 010 的时候，s 取任意值都是不合理的PS : 1*2 的小矩形拼出来的面积必然为偶数若 h*w 为奇数 puts("0")
*/ll ans[12][12] = {{0,1,0,1,0,1,0,1,0,1,0},{1,2,3,5,8,13,21,34,55,89,144},{0,3,0,11,0,41,0,153,0,571,0},{1,5,11,36,95,281,781,2245,6336,18061,51205},{0,8,0,95,0,1183,0,14824,0,185921,0},{1,13,41,281,1183,6728,31529,167089,817991,4213133,21001799},{0,21,0,781,0,31529,0,1292697,0,53175517,0},{1,34,153,2245,14824,167089,1292697,12988816,108435745,1031151241,8940739824},{0,55,0,6336,0,817991,0,108435745,0,14479521761,0},{1,89,571,18061,185921,4213133,53175517,1031151241,14479521761,258584046368,3852472573499},{0,144,0,51205,0,21001799,0,8940739824,0,3852472573499,0}};
int main()
{int h,w;while (Sint2(h,w)==2){if (h==0&&w==0) break; Pllc(ans[w-1][h-1],'\n');}return 0;
}TLE代码：
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
/*0 表示没有覆盖1 表示已经覆盖dp[i][s] 表示第 i 行使用状态 s 的方案数dp[i][s] = ∑dp[i-1][ss] ss 为 枚举的第 i-1行的情况注意：1. ss 中的0表示没有覆盖 ，需要第 i 行在此处放一块 竖着的砖所以 s 和 ss 不能在相同的位置同时为 0即当 ss 在某处是 0的话 s在该处必须是 1 且只能竖着放2. ss 中的1表示已经覆盖 ，故第 i 行在此处可以选择放（1）一块横着的砖或者不放（0）如果放横着的砖，需要两个连续的1，同时上一行也要有2个连续的1比如 ss 是 010 的时候，s 取任意值都是不合理的PS : 1*2 的小矩形拼出来的面积必然为偶数若 h*w 为奇数 puts("0")
*/
ll dp[12][1<<12];
int h,w;
ll ans[12][12];
bool ok(int st)
{int dig[22];int len = 0;while (st){dig[++len] = st&1;st>>=1;}for (int i = 1;i <= len;++i){int t = 0;while (i <= len&&dig[i] == 1)//第一行被覆盖的必然是 横着放的砖 {++i;++t;}if (t > 0){--i;if (t&1) return 0;//横着放的砖连续段必须是偶数 }}return 1;
}
bool check(int s1,int s2)//检查当前行和上一行是否矛盾
{int b1[20] = {0};int b2[20] = {0};for (int i = 0;i < w;++i)//获取状态 {b1[i] = s1&(1<<i);b2[i] = s2&(1<<i);}//若上一行为0，当前行必须为1for (int i = 0;i < w;++i){if (b2[i]==0&&b1[i] == 0) return 0; } //若上一行和当前行都为1，表示当前行是放的横砖for (int i = 0;i < w;++i){int t = 0;while (i < w&&b1[i]&&b2[i]){++i;++t;}if (t > 0){--i;if (t&1) return 0;}} return 1;
}
int main()
{mem(ans,-1);while (Sint2(h,w) == 2){if (h == 0&&w == 0) break;if (w > h) swap(w,h);if (~ans[w][h]) {Pllc(ans[w][h],'\n');continue;}else if ((w*h)&1) {ans[w][h] = 0;}else if (h == 1){ans[w][h] = 1;}else {int V = (1<<w) - 1; mem(dp,0); for (int i = 0;i <= V;++i)//初始化第一行的情况 {if (ok(i)) {dp[1][i] = 1;
// cout<<"state = "<<i<<endl;}else dp[1][i] = 0;}for (int i = 2;i <= h;++i)//枚举后面的行{for (int j = 0;j <= V;++j)//枚举当前行的状态{for (int k = 0;k <= V;++k)//枚举上一行的情况 {if (check(j,k)) {dp[i][j] += dp[i-1][k];
// cout<<"state[i] = "<<j<<" state[i-1] = "<<k<<endl;
// cout<<"dp = "<<dp[i][j]<<endl;}}} } ans[w][h] = dp[h][V];//第h行要铺满啊！ }Pllc(ans[w][h],'\n');}return 0;
}这篇关于POJ 2411 Mondriaan's Dream 据说超时可以打表^_^)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
