POJ 2411.Mondriaan's Dream 解题报告
2024-08-24 02:48:11
题意:
给出n*m (1≤n、m≤11)的方格棋盘,用1*2的长方形骨牌不重叠地覆盖这个棋盘,求覆盖满的方案数。
Solution:
位运算+状态压缩+dp
二进制数(####)代表填完一行后这一行的状态,填满的地方为1,未填的地方为0。
显然在填第i行时,能改变的仅为第i-1行和第i行,因此要满足在填第i行时,第1~i-2行已经全部填满。
DFS一行的状态,要是填完第i行时,第i-1行被填满。
因此两行的状态(p1,p2)满足,~p1=p2;
DFS出所有满足条件的状态对(P1,P2)
①第i行第k位为1,第i-1行第k位为0。(一块骨牌竖直放置)
dfs(k+1,last<<1,now<<1 | 1)
②第i行第k位为0,第i-1行第k位为1。 (第i行空出第k位)
dfs(k+1,last<<1 | 1,now<<1)
③骨牌横向放置。
bfs (k + 2, last << 2 | 3, now << 2 | 3)
转移方程:F[i][sp1]=∑f[i-1][sp2]
代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
using namespace std;
int n, m, x;
LL f[12][1 << 12];
void dfs (int k, int last, int now) {
if (k ==m ) f[x][now] += f[x - 1][last];
if (k > m) return;
dfs (k + 1, last << 1, now << 1 | 1);
dfs (k + 1, last << 1 | 1, now << 1);
dfs (k + 2, last << 2 | 3, now << 2 | 3);
}
int main() {
while (~scanf ("%d %d", &n, &m) ) {
if (n == 0) break;
if (n > m) swap (n, m);
memset (f, 0, sizeof f);
f[0][ (1 << m) - 1] = 1;
for (x = 1; x <= n; x++)
dfs (0, 0, 0);
printf ("%lld\n", f[n][ (1 << m) - 1]);
}
}
最新文章
- hibernate笔记--基于外键的单(双)向的一对一映射关系
- STM32——外部中断EXIT实现
- Calling startActivity() from outside of an Activity
- Mysql调试存储过程最简单的方法
- 文件比对工具(Beyond Compare)
- Android -- TabHost、Fragment、状态保存、通信
- android代码片段二
- Linux 释放cached内存
- ubuntux下apk反编译工具安装
- B-end
- api-gateway实践(04)新服务网关 - 新手入门
- 2018-2019-1 20189210 《LInux内核原理与分析》第四周作业
- 7种清除浮动 (感觉br最好用然而我用的还是overflow)
- 关于istream_iterator<;int>;(cin)和istream_iterator<;int>;()的一点分析
- 步步为营-84-数字转化为金额的Js+enter键取消页面刷新
- ranch 源码分析(三)
- sqlite--一秒20万数据
- PHP + JS 实现大文件分割上传
- EOS account 中的 Threshold 和 weight 使用
- Merkle Tree 概念