POJ2411状压DP（0竖1横）

题意：m*n的矩阵问填多少个1 * 2 的子块可以将其填满的方案数

思路：m*n是奇数时肯定不行，m或n有一个为1肯定只有一种。对于每一行设计状态假设填横着的则为连续的11，填竖着的则设为0，对于下一行来说，如果上一行相同位置如果是0，那么我只能填1，如果上一行相同位置为1，那么我可以填0，如果上一行相同位置为连续的两个1.那么我填11.最终态是dp[m][1<<(n-1)]，因为需要填满，所以最后一行只能是全1.不能出现0，因为出现0需要用下一行的格子补齐；

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N = 1e5+5; ll dp[12][1<<12]; int m,n; void dfs(int i , int s1, int s2, int d){ //printf("%d %d %d %d\n",i,s1,s2,d); if(d == n){ dp[i][s2] += dp[i-1][s1]; }else{ if(s1 & (1<<d)){///前一行第d位填了1， ///dfs(i,s1,s2|(1<<d),d+1);///填1, dfs(i,s1,s2&~(1<<d),d+1);///填0; if(d < n - 1 && (s1 & (1<<(d+1)) )) dfs(i,s1,s2|(1<<d)|(1<<(d+1)),d+2);///填11 //dfs(i,s1,s2,d+2);///填00 }else dfs(i,s1,s2|(1<<d),d+1); } } int jud(int num){ while(num>0){ if(num & 1){ num>>=1; //printf("%d--%d\n",num,!(num&1)); if(!(num&1)) return 0; } num>>=1; } return 1; } int main(){ while(scanf("%d %d",&m,&n)&&m){ if(m*n%2){printf("0\n");continue;} if(m < n)swap(m,n); if(n == 1){printf("1\n");continue;} for(int i = 0 ; i <= (1<<n)-1 ; i++){ ///11横，0竖 dp[1][i] = jud(i); //printf("%lld\n",dp[1][i]); } for(int kk = 2 ; kk <= m ; kk++) for(int i = 0 ; i <= (1<<n)-1 ; i ++) if(dp[kk-1][i] >0) dfs(kk,i,0,0); printf("%lld\n",dp[m][(1<<n)-1]); memset(dp,0,sizeof(dp)); } return 0 ; }