题目描述:给定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; }
相关推荐
不要下载此版的,请下载最新的http://download.csdn.net/source/1664620 离线版的福大acm在线评测OJ系统题目 更新到2009年8月 (注:chm电子书格式化)
RTC2020_EfficientSR FZU-CS510冠军开源方案比赛链接: ://www.dcjingsai.com/v2/cmptDetail.html?id 409比赛团队(团队):FZU-CS510比赛名次及热门: 团队成员:福州大学甘敏教授团队的博士生苏建楠,帝视科技张...
ACM数学_FZU...............绝密..........
安装linux-zhcon-0.2.3.tar.gz,扩张虚拟机硬盘10g,并挂载在/home/fzu./data下,实现window与linux之间的相互共享
今天完成题目:398print( random.uniform(1.1,5.4) ) # 产生 1.1 到 5.4 之间的随机浮点数,区间可以不是整数a=[1,
求最大乘积 的源代码 次题是fzu 4月月赛题 是一道数学题啊
fzu online judge 的几道题,我的解题过程与思路,虽然都是很easy的题目,不过,重在参与嘛,哈哈
2021FZU计算机视觉作业(九)
2021FZU计算机视觉作业(七)
2021FZU计算机视觉作业(八)
2021FZU计算机视觉期末复习
dbc.sw.fzu同学录
fzu大数据基础实验4
java8 源码 InfectStatistic 疫情统计-作业完成流程: 1 fork该仓库到你的仓库,在根目录新建目录,目录名为你的学号 2.复制example下的目录结构到你新建的目录下: 如果你使用c/c++或python,修改src下的文件后缀和...
(This is a collection of documents relating to our Leapfrog Handbook project, including member grouping information forms, task summary documents for each group member, a project diary, and other ...
C#miniword完整版,FZU作业,MINIWORD
FZU软件工程web课程复习资料-整理
FZU2021计算机视觉慕课答案(一)
FZU软件工程操作系统课程复习资料-整理
2021FZU计算机视觉答案(二 )