题目：Mondriaan's Dream
链接：http://poj.org/problem?id=2411
题意：用 1*2 的瓷砖去填 n*m 的地板，问有多少种填法。
思路：
很久很久以前便做过的一道题目，状压DP，当时写得估计挺艰辛的，今天搜插头DP又搜到它，就先用状压DP写了下，顺利多了，没一会就出来了，可惜因为long long没有1A。
思路挺简单，一行一行解决，每一列用1 表示对下一行有影响，用0 表示对下一行没有影响，所以一行最多2048 种可能，然后要筛选一下，因为有些本身就不合理，有些因为上一行的影响变得不合理，然后简单的三重循环搞定，发现以前的代码效率更高，懒得追究了，一起贴出来。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 200
typedef long long LL;
int ans[N],ao;
bool check(int i,int m)
{
int co=,o=;
while(i)
{
o++;
if(i&)
{
if(co&) return false;
else co=;
}
else
{
co++;
}
i>>=;
}
if((m-o)&)
return false;
return true;
}
void find(int m)
{
for(int i=;i<(<<m);i++)
{
if(check(i,m)==)
{
ans[ao++]=i;
}
}
}
void dis(int i,int m)
{
int o=;
while(i)
{
printf("%d",i&);
o++;
i>>=;
}
for(int j=o;j<m;j++)
printf("");
printf("\n");
}
int pre[][],po;
LL dp[][];
bool check_2(int a,int b)
{
while(a)
{
if(a&)
{
if(b&);
else return false;
}
a>>=;
b>>=;
}
return true;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==) break;
ao=;
find(m);
memset(dp,,sizeof(dp));
po=;
for(int i=;i<ao;i++)
{
pre[][po++]=ans[i];
dp[][ans[i]]=;
}
int ko=;
bool v[]={};
for(int i=;i<n;i++)
{
memset(v,,sizeof(v));
for(int k=;k<po;k++)
{
if(v[pre[i-][k]]) continue;
v[pre[i-][k]]=;
for(int j=;j<ao;j++)
{
if(check_2(pre[i-][k],ans[j]))
{
//printf("pre %d ans %d\n",pre[i-1][k],ans[j]);
pre[i][ko++]=ans[j]^pre[i-][k];
dp[i][pre[i][ko-]]+=dp[i-][pre[i-][k]];
}
}
}
po=ko;
}
printf("%I64d\n",dp[n-][]);
}
return ;
}
AC代码--1
#include<stdio.h>
#include<string.h>
#define LL long long
LL dp[][]; // 1：影响到下一行 0：不影响下一行 bool check(int m, int up, int x){
int flag=;
while(m--){
if(x&){
if(flag==) return false;
if(up&) return false;
}
else{
if(up&){
if(flag==) return false;
}
else flag^=;
}
x>>=;
up>>=;
}
if(flag==) return false;
return true;
} int main(){
int n, m;
while(scanf("%d%d", &n, &m)!=EOF){
if(n== && m==) break;
if(n*m%==){
printf("0\n");
continue;
}
memset(dp, , sizeof(dp));
int c = ( << m);
for(int i=; i<c; i++){
if(check(m, , i)){
dp[][i]=;
}
}
for(int i=; i<n; i++){
for(int j=; j<c; j++){
if(dp[i-][j]>){
for(int k=; k<c; k++){
if(check(m, j, k)){
dp[i][k]+=dp[i-][j];
}
}
}
}
}
printf("%I64d\n", dp[n-][]);
}
return ;
}
AC代码--2