Input
Output
Sample Input
1 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0 0
Sample Output
1 0 1 2 3 5 144 51205
题意：给你一个矩形的高和宽，让你用高为1宽为2的小矩形完全填充，不能重叠，不能超出，求出有多少种方案
如高为2，宽为4，有5种
这是状态压缩dp，https://blog.csdn.net/u014634338/article/details/50015825
将状态用二进制比特位表示，
横放为1，竖放对下一行产生影响，为01，如果最后一行全为1，则可以
#include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<cstdio> using namespace std; const int maxn=1e8; typedef long long ll; int n,m; ll dp[15][1<<12]; bool init(int s) { for(int j=0;j<m;)//前面j-1列符合要求，判断j列 { if(s&(1<<j))//第j列为1 { if(j==m-1) return false; if(s&(1<<(j+1)))//j和j+1列都为1，横放 j+=2; else//j为1，j+1为0不可行 return false; } else//j列为0，竖着放，可行 j++; } return true; } bool check(int w,int p) { for(int j=0;j<m;) { if(w&(1<<j))//第i行j列为1 { if(p&(1<<j))//第i-1行j列也为1，第i行横放 { //所以第i行和i-1行的第j+1都为1，否则非法 if(j==m-1|| !(w&1<<(j+1))|| !(p&1<<(j+1))) return false; else j+=2; } else j++; } else { if(p&(1<<j)) j++; else return false; } } return true; } void solve() { int t=(1<<m)-1; memset(dp,0,sizeof(dp)); for(int i=0;i<=t;i++) { if(init(i)) dp[1][i]=1; } for(int i=2;i<=n;i++) { for(int j=0;j<=t;j++)//第i行状态 { for(int k=0;k<=t;k++)//第i-1行的状态 { if(check(j,k)) dp[i][j]+=dp[i-1][k]; } } } printf("%lld\n",dp[n][t]); } int main() { while(~scanf("%d%d",&n,&m)) { if(n==0||m==0)break; if(n&1 && m&1)//如果m，n都为奇数，面积为奇，不可能完全覆盖 { printf("0\n"); continue; } if(n<m) swap(n,m); solve(); } return 0; }
A - Mondriaan's Dream （状态压缩DP）
原文：https://www.cnblogs.com/ylrwj/p/12024885.html