题目：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，当前行必须为1
for (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;
}
