《算法竞赛进阶指南》0x56 状态压缩DP 经典拼图问题
题目链接：https://www.acwing.com/problem/content/description/293/
题目给出一个n*m的方格，问用1*2的方块去拼，有多少种方案，由于每一行只跟上一行的状态有关系，所以可以把行数作为“阶段”，其次，每行的状态用01表示，0表示对下一行没有影响，1表示需要下一行拼另一半，这样的话状态设计就是前i行且第i行的状态是j的方案的数量。转移的时候注意，第i-1行是1的时候下面一个一定是0，第i-1行是0的时候是没有影响的，所以两个状态j&k==0，而且除了1下面的0以外的地方，其他地方都是通过横着的1*2方块去拼的，所以一定0一定是连续的偶数，这里可以先预处理出来，处理的时候设置一个1位二进制数记录，并且在假设第m位是1的情况之下把最后一段连续0也算在里面。
代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; ll f[12][1<<11]; bool v[1<<11]; int n,m; int main(){ while(cin>>n>>m && n){ memset(f,0,sizeof f); for(int i=0;i<1<<m;i++){ int has_odd=0,cnt=0; for(int j=0;j<m;j++){ if(i>>j & 1)has_odd|=cnt,cnt=0; else cnt^=1; } v[i]=has_odd|cnt ? 0 : 1; } f[0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<1<<m;j++){ for(int k=0;k<1<<m;k++){ if((j&k)==0 && v[j|k]) f[i][j]+=f[i-1][k]; } } } cout<<f[n][0]<<endl; } }