现在的位置: 首页 > 综合 > 正文

FZU 华容道(http://hi.baidu.com/chenwenwen0210/item/f084741a84c9dbee39cb3087)

2019年11月15日 ⁄ 综合 ⁄ 共 1288字 ⁄ 字号 评论关闭

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;
}

抱歉!评论已关闭.