解法参考博客https://blog.csdn.net/u013480600/article/details/19569291
一种做法是先打出所有的状态，即满足上下配对的所有可能方案，然后再逐行进行枚举计数
dp[i][s]=sum{dp[i-1][t]},t是所有和s配对的状态
打状态时要注意如果i-1的j是0，那么i的j必定是1，i剩下的位置要必须一对对填入1，也可以用0填入，即枚举i行的横放砖块的起始位置k即可，如果i-1的k或k+1有一个不是1，那么显然不能放下
/* 对于每一行，用11表示一个横放的方块，用0表示竖放方块的第一格，1表示竖放方块的第二格 枚举i-1行的状态，推出i行的状态 如果i-1行的j位置是0，那么第i行的j必须是1，第i行剩下的地方要么填连续两个1要么填0 第n行的状态必须都是1 */ #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define ll long long ll dp[15][1<<13]; int n,m,w,path[5000000][2];//所有可能的配对方案 void get(int m){ for(int i=0;i<=(1<<m)-1;i++) for(int j=0;j<=(1<<m)-1;j++){ int ok=1; for(int k=0;k<m;k++) if(ok){ if( !(i&(1<<k)) ){//i的第k位是0 if(!(j&(1<<k))){ ok=0;break; } } else{//i的第k位是1，其实是在枚举j状态横放的起点位置 if(!(j&(1<<k)))continue;//j的第k位是0 ++k; if(k>=m || !(i&(1<<k))){//i没有第k+1位或者i的第k+1位是0，所以j在k位置不可能横放了 ok=0;break; } else if( (j&(1<<(k-1))) && !(j&(1<<k)) ){//j的状态是10，显然不可能 ok=0;break; } } } if(ok)path[w][0]=i,path[w++][1]=j; } } int main(){ while(cin>>n>>m,n){ w=0; if(m>n)swap(n,m); get(m); memset(dp,0,sizeof dp); dp[0][(1<<m)-1]=1; for(int i=0;i<n;i++) for(int j=0;j<w;j++) dp[i+1][path[j][1]]+=dp[i][path[j][0]]; printf("%lld\n",dp[n][(1<<m)-1]); } }另外一种解法
/* 用0和1表示某个位置放不放砖块，如果是0则表示让下一行来补，如果是1则有两种可能，一种是横放，一种是填补上一行的0 对应这三种情况，可以搜索出所有可能的配对情况 */ #include<bits/stdc++.h> using namespace std; #define ll long long ll dp[15][1<<15]; int path[5000000][2],n,m,w; void get(int c,int pre,int now){ if(c>m)return; else if(c==m){ path[w][0]=pre; path[w++][1]=now; return; } get(c+1,(pre<<1)|1,now<<1);//后一行不放，前一行必定是1 get(c+1,pre<<1,(now<<1)|1);//前一行0，后一行必定是1 get(c+2,(pre<<2)|3,(now<<2)|3);//前一行横放，后一行也是横放 } int main(){ while(cin>>n>>m,m){ w=0; if(m>n)swap(n,m); get(0,0,0); memset(dp,0,sizeof dp); dp[0][(1<<m)-1]=1;//初始条件不可忽略！ for(int i=0;i<n;i++) for(int j=0;j<w;j++) dp[i+1][path[j][1]]+=dp[i][path[j][0]]; printf("%lld\n",dp[n][(1<<m)-1]); } }最后是轮廓线解法：遍历一次方格，每扫到一个方格时枚举所有可能的轮廓线，然后由上一个格子（上一个状态的轮廓线）推出当前状态的轮廓线所对应的摆放方案数，以此推到最后一个格子
使用滚动dp数组，覆盖之前无效的信息即可
/* 轮廓线解法 */ #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define ll long long ll dp[2][1<<13]; int n,m,cur; void update(int a,int b){//a是包含m位的旧状态，b是包含m+1位的新状态 if(b&(1<<m))//如果b的首位是1才进行转移，即如果b的首位是0的话是不成立的 dp[cur][b^(1<<m)]+=dp[cur^1][a]; } int main(){ while(cin>>n>>m,m){ if(m>n)swap(m,n); memset(dp,0,sizeof dp); cur=0; dp[0][(1<<m)-1]=1;//边际条件算第一种方案：需要由这个初始状态推导出其他状态 for(int i=0;i<n;i++) for(int j=0;j<m;j++){ cur^=1; memset(dp[cur],0,sizeof dp[cur]);//把上一轮的状态清零 for(int k=0;k<(1<<m);k++){//枚举当前所有可能的轮廓线状态 //三种可能 update(k,k<<1);//[i,j]不放 if(i && !(k&(1<<(m-1))))update(k,(k<<1)^(1<<m)^1);//向上摆放 if(j && !(k&1))update(k,(k<<1)^3);//向左摆放 } } printf("%lld\n",dp[cur][(1<<m)-1]); } }
转载于:https://www.cnblogs.com/zsben991126/p/10359187.html
