ZOJ1100 Mondriaan's Dream
2024-09-13 21:49:09
题目链接:QAQ
大致题意:有一个m行n列的矩阵,用1*2的骨牌(可横放或竖放)完全覆盖,骨牌不能重叠,有多少种不同的覆盖的方法?
Solution:
\(n,m\le11\),肯定是不能暴力的,又类似棋盘问题,一下就能想到状压dp
对于每一列(或每一行)的状态用二进制表示,0表示放了,1表示没放,在转换回十进制存储。
然后枚举一列的所有状态,看它可以转移到哪些状态,然后统计答案就行了。
最后应该输出f[n+1][0],而不是f[n][n]。本题需要long long。
Code:
#include<cstdio>
#include<cstring>
#define N 10001
#define ll long long
using namespace std;
int n,m;
ll dp[15][2051];
int a[15],b[15],c[2051][2051];
void dfs(int x,int state){
if(x==m+1){
int k=0;
for(int i=1;i<=m;i++) k=(k<<1)+b[i];
c[state][k]=1;
return ;
}
if(!a[x]){
b[x]=1;
dfs(x+1,state);
if(!a[x+1]&&x+1<=m){
b[x]=b[x+1]=0;
dfs(x+2,state);
}
}else b[x]=0,dfs(x+1,state);
}
signed main(){
begin:
scanf("%d%d",&n,&m);
if(n==0&&m==0) return 0;
memset(c,0,sizeof(c));
memset(dp,0,sizeof(dp));
int num=(1<<m)-1;
for(int i=0;i<=num;i++){
int k=i;
for(int j=m;j;j--) a[j]=k%2,k>>=1;
dfs(1,i);
}dp[1][0]=1;
for(int k=1;k<=n;k++)
for(int i=0;i<=num;i++)
for(int j=0;j<=num;j++)
dp[k+1][j]=dp[k+1][j]+(c[i][j]*dp[k][i]);
printf("%lld\n",dp[n+1][0]);
goto begin;
}
最新文章
- 复旦大学2015--2016学年第一学期(15级)高等代数I期末考试第八大题解答
- [AHOI 2006][BZOJ 1269]文本编辑器editor
- 第二百三十三天 how can I 坚持
- CentOS6.5安装MySQL及完全卸载
- 1.dubbo的安装 quickstart
- CocoaPods的安装使用和常见问题
- sphinx set several dates as filter
- 用js制作日期 2017-03-23
- CentOS 7中允许远程连接mariadb数据库
- Java并发编程之并发容器
- BTARN 接收消息流以3A7为例
- mac 中vim永久显示行号、开启语法高亮
- 洛谷.1919.[模板]A*B Problem升级版(FFT)
- InstallShield 读注册表函数 RegDBGetKeyValueEx ()执行失败
- Git 版本控制管理(二)
- 基于jQuery点击缩略图右侧滑出大图特效
- PHP主动断开与浏览器的连接
- 如何将String转换为int
- iOS网络NSURLConnection使用详解
- EMC检测标准