摘要：
标准时间>；16elseco=0；27{28voidfind（intm）29{30for（inti=0；intm）39{40into=0；intb）54{55while（a）56{57if（a&；1）58{59if（b&；76po=0；77for（inti=0；83boolv[2050]＝{0}；i<；87for（intk=0；j<；
题目：Mondriaan's Dream
链接：http://poj.org/problem?id=2411
题意：用 1*2 的瓷砖去填 n*m 的地板，问有多少种填法。
思路：
很久很久以前便做过的一道题目，状压DP，当时写得估计挺艰辛的，今天搜插头DP又搜到它，就先用状压DP写了下，顺利多了，没一会就出来了，可惜因为long long没有1A。
思路挺简单，一行一行解决，每一列用1 表示对下一行有影响，用0 表示对下一行没有影响，所以一行最多2048 种可能，然后要筛选一下，因为有些本身就不合理，有些因为上一行的影响变得不合理，然后简单的三重循环搞定，发现以前的代码效率更高，懒得追究了，一起贴出来。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #define N 200 5 typedef long long LL; 6 int ans[N],ao; 7 bool check(int i,int m) 8 { 9 int co=0,o=0; 10 while(i) 11 { 12 o++; 13 if(i&1) 14 { 15 if(co&1) return false; 16 else co=0; 17 } 18 else 19 { 20 co++; 21 } 22 i>>=1; 23 } 24 if((m-o)&1) 25 return false; 26 return true; 27 } 28 void find(int m) 29 { 30 for(int i=0;i<(1<<m);i++) 31 { 32 if(check(i,m)==1) 33 { 34 ans[ao++]=i; 35 } 36 } 37 } 38 void dis(int i,int m) 39 { 40 int o=0; 41 while(i) 42 { 43 printf("%d",i&1); 44 o++; 45 i>>=1; 46 } 47 for(int j=o;j<m;j++) 48 printf("0"); 49 printf(" "); 50 } 51 int pre[12][410000],po; 52 LL dp[12][2050]; 53 bool check_2(int a,int b) 54 { 55 while(a) 56 { 57 if(a&1) 58 { 59 if(b&1); 60 else return false; 61 } 62 a>>=1; 63 b>>=1; 64 } 65 return true; 66 } 67 int main() 68 { 69 int n,m; 70 while(scanf("%d%d",&n,&m)!=EOF) 71 { 72 if(n==0&&m==0) break; 73 ao=0; 74 find(m); 75 memset(dp,0,sizeof(dp)); 76 po=0; 77 for(int i=0;i<ao;i++) 78 { 79 pre[0][po++]=ans[i]; 80 dp[0][ans[i]]=1; 81 } 82 int ko=0; 83 bool v[2050]={0}; 84 for(int i=1;i<n;i++) 85 { 86 memset(v,0,sizeof(v)); 87 for(int k=0;k<po;k++) 88 { 89 if(v[pre[i-1][k]]) continue; 90 v[pre[i-1][k]]=1; 91 for(int j=0;j<ao;j++) 92 { 93 if(check_2(pre[i-1][k],ans[j])) 94 { 95 //printf("pre %d ans %d ",pre[i-1][k],ans[j]); 96 pre[i][ko++]=ans[j]^pre[i-1][k]; 97 dp[i][pre[i][ko-1]]+=dp[i-1][pre[i-1][k]]; 98 } 99 } 100 } 101 po=ko; 102 } 103 printf("%I64d ",dp[n-1][0]); 104 } 105 return 0; 106 }
1 #include<stdio.h> 2 #include<string.h> 3 #define LL long long 4 LL dp[11][2048]; 5 6 // 1：影响到下一行 0：不影响下一行 7 8 bool check(int m, int up, int x){ 9 int flag=0; 10 while(m--){ 11 if(x&1){ 12 if(flag==1) return false; 13 if(up&1) return false; 14 } 15 else{ 16 if(up&1){ 17 if(flag==1) return false; 18 } 19 else flag^=1; 20 } 21 x>>=1; 22 up>>=1; 23 } 24 if(flag==1) return false; 25 return true; 26 } 27 28 int main(){ 29 int n, m; 30 while(scanf("%d%d", &n, &m)!=EOF){ 31 if(n==0 && m==0) break; 32 if(n*m%2==1){ 33 printf("0 "); 34 continue; 35 } 36 memset(dp, 0, sizeof(dp)); 37 int c = (1 << m); 38 for(int i=0; i<c; i++){ 39 if(check(m, 0, i)){ 40 dp[0][i]=1; 41 } 42 } 43 for(int i=1; i<n; i++){ 44 for(int j=0; j<c; j++){ 45 if(dp[i-1][j]>0){ 46 for(int k=0; k<c; k++){ 47 if(check(m, j, k)){ 48 dp[i][k]+=dp[i-1][j]; 49 } 50 } 51 } 52 } 53 } 54 printf("%I64d ", dp[n-1][0]); 55 } 56 return 0; 57 }