FZU 华容道
题目描述:给定4*N的矩形格子。在里面填上1*2,2*1,1*1,2*2的块,其中2*2的真必需且并只能使用一次。其他的随意。
求使得4*N的格子全部填满的总方法数,块之间不能重叠。
解法:状态压缩DP,dp[i][j][k]表示前面i-1行都已经摆放完毕,第i行的摆放二进制状态为j,k表示2*2的方块是否已经摆放,放过了就是1,没放过就是0.
初值dp[0][(1<<4)-1][0]=1
递推的时候直接枚举i-1行的状态,然后深搜,使得i-1行摆满,第i行的状态加上相应的方法数。
总复杂度n*(1<<4)*(1<<4)
最后输出dp[n+1][0][1]
即第n+1行未摆放,2*2已经摆放的状态数目。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <climits> #include <numeric> #include <vector> #include <set> using namespace std; //typedef __int64 lld; const int MAX = 1<<5; int dp[6][MAX][2]; void DFS(int s,int cao,int t,int row,int v,int deep) { if(deep>=4) { if(s==(1<<4)-1) { dp[row][t][cao]+=v; } return ; } if((1<<deep)&s) { DFS(s,cao,t,row,v,deep+1); } else { //yi ge DFS(s|(1<<deep),cao,t,row,v,deep+1); //yi hen if(deep+1<4&& ((1<<(deep+1))&s)==0) { DFS(s|(1<<deep)|(1<<(deep+1)),cao,t,row,v,deep+1); } //yi shu if(((1<<deep)&t)==0) { DFS(s|(1<<deep),cao,t|(1<<deep),row,v,deep+1); } if(cao==0) { if(deep+1<4&& ((1<<(deep+1))&s)==0 &&((1<<deep)&t)==0 &&((1<<(deep+1))&t)==0) { int z=(1<<deep)|(1<<(deep+1)); DFS(s|z,cao+1,t|z,row,v,deep+1); } } } } int main() { int T,n; int i,j,k; memset(dp,0,sizeof(dp)); dp[0][(1<<4)-1][0]=1; for(i=1;i<6;i++) { for(j=0;j<(1<<4);j++) { for(k=0;k<2;k++) { if(dp[i-1][j][k]==0)continue; DFS(j,k,0,i,dp[i-1][j][k],0); } } } scanf("%d",&T); while(T--) { scanf("%d",&n); printf("%d\n",dp[n+1][0][1]); } return 0; }