首页 > 编程语言 >《算法竞赛进阶指南》 第六章 291. 蒙德里安的梦想 状态压缩DP

《算法竞赛进阶指南》 第六章 291. 蒙德里安的梦想 状态压缩DP

时间:2024-04-20 17:12:30浏览次数:26  
标签:11 return 蒙德里安 int state 测试用例 输入 DP 进阶

https://www.acwing.com/problem/content/293/

求把 N×M 的棋盘分割成若干个 1×2 的长方形,有多少种方案。
例如当 N=2,M=4 时,共有 5 种方案。当 N=2,M=3时,共有 3 种方案。
如下图所示:

输入格式
输入包含多组测试用例。

每组测试用例占一行,包含两个整数 N和 M。

当输入用例 N=0,M=0时,表示输入终止,且该用例无需处理。

输出格式
每个测试用例输出一个结果,每个结果占一行。

数据范围
1≤N,M≤11
输入样例:
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
输出样例:
1
0
1
2
3
5
144
51205

解答
使用数字的二进制表示方块的摆放
1 则表示 竖直放置,下一行对应的列 则需要标记为0 表示不放才可行
0 表示不放 上一行对应的列是竖放的 或者表示横放的一部分。
所以抛开上一行的影响(curr | prev),必须偶数个0连在一起。
同时两行相同的位置上不应该出现两个1(curr&prev)

代码如下 TLE了

// 291. 蒙德里安的梦想 jichu.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <assert.h>
#include <cstring>

using namespace std;
/*
https://www.acwing.com/problem/content/293/
求把 N×M 的棋盘分割成若干个 1×2 的长方形,有多少种方案。
例如当 N=2,M=4 时,共有 5 种方案。当 N=2,M=3 时,共有 3 种方案。

如下图所示:
2411_1.jpg

输入格式
输入包含多组测试用例。
每组测试用例占一行,包含两个整数 N 和 M。
当输入用例 N=0,M=0 时,表示输入终止,且该用例无需处理。

输出格式
每个测试用例输出一个结果,每个结果占一行。

数据范围
1≤N,M≤11
输入样例:
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
输出样例:
1
0
1
2
3
5
144
51205


1 2
2 2
3 2
*/

const int N = 11;
int dp[N+5][1<<N];
int n, m;

int getN(int state, int idx) {
	return (state >> idx) & 1;
}

bool check1(int state) {
	for (int i = 0; i < m;) {
		if (getN(state, i) == 0 && (i == m - 1 || getN(state, i + 1) == 1)) {
			return false;
		}else if (getN(state, i) == 0 && getN(state, i + 1) == 0) {
			i = i + 2;
		}else if (getN(state, i) == 1) {
			i++;
		}else{
			assert(0);
		}
	}

	return true;
}


bool check2(int prev, int curr) {
	int state = prev & curr;
	if (state != 0) return false;
	if (check1(prev | curr) == false) return false;
	return true;
}


int main()
{
	while (cin >> n >> m) {
		if (n == 0 && m == 0) break;
		memset(dp, 0, sizeof dp);
		dp[0][0] = 1;
		for (int i = 0; i <= n; i++) {
			int debug = 0;
			for (int curr = 0; curr < 1 << m; curr++) {
				//检查当前状态是否合法
				//if (check1(curr) == false) { continue; }
				for (int next = 0; next < 1 << m; next++) {
					//检查下一行的状态能和当前匹配
					//那么下一行状态增加对应的方案数
					if (check2(curr, next) == true) {
						dp[i + 1][next] += dp[i][curr];
					}
				}
			}
		}

		cout << dp[n][0] << endl;
	}

	return 0;
}

我的视频空间

标签:11,return,蒙德里安,int,state,测试用例,输入,DP,进阶
From: https://www.cnblogs.com/itdef/p/18147888

相关文章

  • Java 集合进阶使用(List Map Set)
    CollectionCollection是其子集的父类,所以可以使用多态的规矩,比如:创建一个ArrayList对象,用Collection接收Collection<Integer>collection=newArrayList<>();注意:Collection为接口,不能直接创建对象,但可以利用其子类,使用Collection方法,就如上方代码一样Collection......
  • 2023 5月 dp做题记录
    目录5月dp做题记录P1064[NOIP2006提高组]金明的预算方案P1941[NOIP2014提高组]飞扬的小鸟P2679[NOIP2015提高组]子串P1850[NOIP2016提高组]换教室P2831[NOIP2016提高组]愤怒的小鸟P5020[NOIP2018提高组]货币系统P6064[USACO05JAN]NaptimeGP9344去年天......
  • 2023 6月 dp做题记录
    目录6月dp做题记录P5664[CSP-S2019]Emiya家今天的饭P8867[NOIP2022]建造军营[ARC115E]LEQandNEQP3800Power收集P3594[POI2015]WIL6月dp做题记录P5664[CSP-S2019]Emiya家今天的饭分析条件,我们要选出来的菜的集合需要满足的限制,集合不为空和烹饪方法互不相同都好......
  • 2023 7月 dp做题记录
    目录7月dp做题记录TheBakeryP5785[SDOI2012]任务安排P3195[HNOI2008]玩具装箱P3648[APIO2014]序列分割7月dp做题记录TheBakery这道题的状态转移并不难列,经典的分段问题,设状态\(dp_{i,j}\)表示前\(i\)个数字分了\(j\)段的最大价值,转移可以写成\(dp_{i,j}=\max(......
  • [dpdk] rte_flow
     以下内容直接来自官网文档的整理。更精准的描述请阅读文档:https://doc.dpdk.org/guides/prog_guide/rte_flow.html一rte_flow是干嘛的一组用来创建自定义规则的api,该规则可以改变网络流量的命运,以及查询计数。 二规则啥样1match+actionmatch包括:两类,A报文内容(按......
  • led驱动程序进阶-使用面向对象的思想完成led驱动程序
    上一篇文章实现了一个led驱动程序的模板,该模板虽然只是用于led驱动程序的编写,但是对于其它任何设备的驱动程序编写,其面向对象的思想都是可以借鉴和参考的。任何看似高深的技巧,都是从简单出发的,逐步深入。独孤九剑的最高境界就是无剑、无招,所有高深的变化都是从最基本的原理出发!本......
  • 区间dp思想
    删数链接:https://www.luogu.com.cn/problem/P2426题目描述有\(N\)个不同的正整数\(x_1\),\(x_2\),...,\(x_N\)排成一排,我们可以从左边或右边去掉连续的\(i\)\((1\lei\len)\)个数(只能从两边删除数),剩下\(N-i\)个数,再把剩下的数按以上操作处理,直到所有的数都被删......
  • 概率dp四题(青蛙跳、吸血鬼、rating、k小姐的点赞之谜)
    青蛙跳Description有\(n\)个荷叶按顺序依次排列开,编号为\(1\)到\(n\),现在有只青蛙在编号为\(n\)的荷叶上。它现在自由愉快的跳跃,如果他在编号为\(i\)的荷叶上,它会等概率的跳到编号为\([1,i]\)的荷叶上,求它跳到编号为\(1\)的荷叶上的期望步数。Samples53.083333......
  • [dp 小计] wqs 二分
    天才算法!国外叫Alienstrick(外星人trick),真的太强了。其实是因为IOI2016Aliens这道题考了这个算法才开始普及。解决问题wqs二分一般用来解决如下问题。给定\(n\)个数,求强制选\(m\)个的价值最大。如果不是强制选\(m\)个,这类问题很好做。现在问题就是怎么取消......
  • Pyecharts制作动态GDP柱状图
    学习使用pyecharts制作动态柱状图使用csv模块进行csv数据文件处理importcsvfrompyecharts.chartsimportBar,Timelinefrompyecharts.optionsimport*frompyecharts.globalsimportThemeTypedefdealCSVFile():"""读取处理csv数据文件:retu......