【动态规划】【状态压缩】LCP04 覆盖

作者推荐

【广度优先搜索】【网格】【割点】【 推荐】1263. 推箱子

本文涉及知识点

动态规划汇总

LCP04 覆盖

你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。
输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。
输出：一个整数，代表最多能在棋盘上放的骨牌数。
示例 1：
输入：n = 2, m = 3, broken = [[1, 0], [1, 1]]
在这里插入图片描述

输出：2
解释：我们最多可以放两块骨牌：[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。（见下图）
示例 2：
输入：n = 3, m = 3, broken = []
输出：4
解释：下图是其中一种可行的摆放方式
在这里插入图片描述
限制：
1 <= n <= 8
1 <= m <= 8
0 <= b <= n * m

动态规划

动态规划状态数

mask &(1 << j) 表示第j列空闲，没有放置骨牌，也没有损坏。其它位置不限：损坏、骨牌、空闲皆可。
pre[mask] 表示第i行开始处理时，上一行状态为mask的最多骨牌数。
dp1[mask] 表示处理完第i行的竖放后，最多骨牌数。
dp2[mask] 表示处理完第i行的竖放横放后，最多骨牌数。

动态规划的转移方程

mask1 是上一行的状态。
mask2 = mask ^ 当前行坏掉的位置。
mask3 = mask1 & mask2
枚举所有 mask4(竖放），mask4是mask所有非0子序列。每个mask1都要枚举mask4
mask5是竖放完的状态 mask2 ^ mask4。
枚举mask5的所有子序列mask6，横放的状态，合法状态：数量必须是偶数，两两挨在一起。
时间复杂度: O(m3n)

动态规划的初始状态

pre[0]=0，其它-100。

动态规划的填表顺序

按行处理。

动态规划的返回值

pre的最大值。

代码

核心代码

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
	*seft = max(*seft, other);
}
class CBitCounts
{
public:
	CBitCounts(int iMaskCount)
	{
		for (int i = 0; i < iMaskCount; i++)
		{
			m_vCnt.emplace_back(bitcount(i));
		}
	}
	template<class T>
	int bitcount(T x) {
		int countx = 0;
		while (x) {
			countx++;
			x &= (x - 1);
		}
		return countx;
	}
	vector<int> m_vCnt;
};

class CEnumMask2
{
public:
	CEnumMask2(int iMaskCount):m_iMaskCount(iMaskCount)
	{

	}
	template<class GetMask2,class On>
	void Enum(GetMask2 getMask2,On on )
	{
		for (int mask1 = 0; mask1 < m_iMaskCount; mask1++)
		{
			const int mask2 = getMask2(mask1);
			for (int mask3 = mask2; mask3; mask3 = mask2 & (mask3 - 1))
			{
				on(mask1, mask2, mask3);
			}
		}
	}
	const int m_iMaskCount;
};
class Solution {
public:
	int domino(int n, int m, vector<vector<int>>& broken) {
		const int iMaskCount = 1 << m;
		vector<int> vCan(n, iMaskCount-1);
		for (const auto& v : broken)
		{
			vCan[v[0]] ^= (1 << v[1]);
		}		
		CBitCounts bitCnt(iMaskCount);
		vector<int> vVilidH(iMaskCount,-100);
		vVilidH[0] = 0;
		for (int i = 1; i < iMaskCount; i++)
		{
			int end = i & (-i);
			int end1 = end * 2;
			if (i & end1)
			{
				vVilidH[i] = 1 + vVilidH[i ^ end ^ end1];
			}
		}
		vector<int> pre(iMaskCount, -100);
		pre[0] = 0;
		CEnumMask2 enumMask(iMaskCount);
		for (int r = 0; r < n; r++)
		{
			vector<int> dp1(iMaskCount, -100);
			dp1[vCan[r]] = *std::max_element(pre.begin(), pre.end());//不竖放
			enumMask.Enum([&](int mask1) {return vCan[r] & mask1; }, [&](int mask1, int mask2, int mask3)
				{MaxSelf(&dp1[vCan[r] ^ mask3], pre[mask1] + bitCnt.m_vCnt[mask3]); });
			vector<int> dp2 = dp1 ;//不横放
			enumMask.Enum([](int mask1) {return mask1; }, [&](int mask1, int mask2, int mask3)
				{if (vVilidH[mask3] <= 0)
			{
				return;
			}
			MaxSelf(&dp2[mask1 ^ mask3], dp1[mask1] + vVilidH[mask3]); });
			pre.swap(dp2);
		}
		return *std::max_element(pre.begin(), pre.end());
	}
};

测试用例


template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	int m,n;
	vector<vector<int>> broken;
	{
		Solution sln;
		n = 2, m = 3, broken = { {0, 0},{0, 1} };
		auto res = sln.domino(n, m, broken);
		Assert(2, res);
	}
	{
		Solution sln;
		n = 2, m = 3, broken = { {1, 0},{1, 1} };
		auto res = sln.domino(n, m, broken);
		Assert(2, res);
	}
	{
		Solution sln;
		n = 3, m = 3, broken = {  };
		auto res = sln.domino(n, m, broken);
		Assert(4, res);
	}
	{
		Solution sln;
		n = 4, m = 3, broken = { {1,0},{1,1} };
		auto res = sln.domino(n, m, broken);
		Assert(5, res);
	}
	{
		Solution sln;
		n = 3, m = 4, broken = { {2,2},{2,3} };
		auto res = sln.domino(n, m, broken);
		Assert(5, res);
	}

}

优化

枚举所有合法状态，再枚举竖放状态。不用枚举前一行的状态。竖放的状态就是前一行状态。

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
	*seft = max(*seft, other);
}
class CBitCounts
{
public:
	CBitCounts(int iMaskCount)
	{
		for (int i = 0; i < iMaskCount; i++)
		{
			m_vCnt.emplace_back(bitcount(i));
		}
	}
	template<class T>
	int bitcount(T x) {
		int countx = 0;
		while (x) {
			countx++;
			x &= (x - 1);
		}
		return countx;
	}
	vector<int> m_vCnt;
};

class Solution {
public:
	int domino(int n, int m, vector<vector<int>>& broken) {
		const int iMaskCount = 1 << m;
		vector<int> vCan(n, iMaskCount-1);
		for (const auto& v : broken)
		{
			vCan[v[0]] ^= (1 << v[1]);
		}		
		CBitCounts bitCnt(iMaskCount);
		vector<int> vHMax(iMaskCount);	
		for (int i = 1; i < iMaskCount; i++)
		{
			int end = i & (-i);
			int end1 = end * 2;
			vHMax[i] = (i & end1) ? (1 + vHMax[i ^ end ^ end1]) : (vHMax[i ^ end]);
		}
		vector<int> pre(iMaskCount, -100);
		pre[0] = 0;
		for (int r = 0; r < n; r++)
		{
			vector<int> dp(iMaskCount, -100);
			dp[vCan[r]] = pre[0];
			for (int mask = vCan[r]; mask; mask = (mask - 1) & vCan[r])
			{//当前行放置阵了骨牌的位置
				for (int maskH = mask; ; maskH = (maskH - 1) & mask)
				{
					MaxSelf(&dp[vCan[r] ^ mask], vHMax[mask ^ maskH] + bitCnt.m_vCnt[maskH] + pre[maskH]);
					if (0 == maskH)
					{
						break;
					}
				}
			}	
			pre.swap(dp);
		}
		return *std::max_element(pre.begin(), pre.end());
	}
};

2023年2月版

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}

class Solution {
public:
int domino(int R, int C, vector<vector>& broken) {
m_iMaskNum = 1 << C ;
vector vRowMask(R, m_iMaskNum - 1);
for (const auto& v : broken)
{
vRowMask[v[0]] &= ~(1 << v[1]);
}
vector pre(m_iMaskNum, -1);
pre[0] = 0;
for (int r = 0; r < R; r++)
{
vector dp(m_iMaskNum, -1);
for (int pr = 0; pr < m_iMaskNum; pr++)
{
const int& iPreNum = pre[pr];
if (-1 == iPreNum)
{
continue;
}
const int iCurRMask = vRowMask[r];
const int iMaxVMask = iCurRMask & pr;
//vMask枚举所有的竖放
for (int vMask = iMaxVMask;; vMask = iMaxVMask & (vMask - 1))
{
const int iMaxHMask = iCurRMask &(~vMask);
for (int hMask = iMaxHMask;; hMask = iMaxHMask& (hMask - 1))
{
const int iHNum = GetHNum(hMask);
if (iHNum < 0)
{
continue;
}
dp[iMaxHMask & ~hMask] = max(dp[iMaxHMask & ~hMask], iPreNum + iHNum + bitcount(vMask));
if (0 == hMask)
{
break;
}
}
if (0 == vMask)
{
break;
}
}
}
pre.swap(dp);
}
return *std::max_element(pre.begin(), pre.end());
}
int GetHNum(int iMask)
{
int iNum = 0;
while (iMask)
{
int iEndMask = (iMask&(-iMask));
int iPreMask = iEndMask << 1;
if (!(iMask & iPreMask))
{
return -1;
}
iMask -= iEndMask;
iMask -= iPreMask;
iNum++;
}
return iNum;
}
int m_iMaskNum;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/406856.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

C#学习总结

C#学习总结

1、访问权限 方法默认访问修饰符&#xff1a;private 类默认访问修饰符&#xff1a;internal 类的成员默认访问修饰符&#xff1a;private 2、UserControl的使用 首先添加用户控件 使用时一种是通过代码添加&#xff0c;一种是通过拖动组件到xaml中
阅读更多...
音频的“隐形保镖”——音频数字水印

音频的“隐形保镖”——音频数字水印

在互联网时代&#xff0c;多媒体数字资源可以快捷地传播和获取&#xff0c;但同时也导致了数字音频产品的非法扩散、非法拷贝和非法篡改猖獗&#xff0c;数字音频产品的完整性和版权保护问题越来越凸显。文档和图像可以添加水印&#xff0c;音频同样可以添加水印&#xff0c;让…
阅读更多...
【递归版】归并排序算法（1）

【递归版】归并排序算法（1）

目录 MergeSort归并排序 整体思想 图解分析 代码实现 时间复杂度 递归&归并排序VS快速排序 MergeSort归并排序 归并排序&#xff08;MERGE-SORT&#xff09;是建立在归并操作上的一种有效的排序算法&#xff0c;该算法是采用分治法&#xff08;Divide and Conquer&a…
阅读更多...
堆排序法的名字由来，排序步骤是什么，最坏情况下的排序次数如何计算得来的呢？

堆排序法的名字由来，排序步骤是什么，最坏情况下的排序次数如何计算得来的呢？

问题描述&#xff1a;堆排序法的名字由来&#xff0c;排序步骤是什么&#xff0c;最坏情况下的排序次数如何计算得来的呢&#xff1f; 问题解答&#xff1a; 堆排序法的名字来源于它使用了堆这种数据结构。堆是一种特殊的树形数据结构&#xff0c;具有以下特点&#xff1a;在…
阅读更多...
基于RK3399 Android11适配OV13850 MIPI摄像头

基于RK3399 Android11适配OV13850 MIPI摄像头

目录 1、原理图分析2、编写和配置设备树3、调试方法4、遇到的问题与解决5、补丁 1、原理图分析 从上图可看出&#xff0c;我们需要关心的&#xff0c;①MIPI数据和时钟接口使用的是MIPI_TX1/RX1 ②I2C使用的是I2C4总线 ③RST复位引脚使用的是GPIO2_D2 ④PWDN使用的是GPIO1_C7 ⑤…
阅读更多...
A星寻路算法详解

A星寻路算法详解

A星寻路算法 前言 A星寻路算法是静态路网中求解最短路径最有效的直接搜索方法&#xff0c;也是解决许多搜索问题的有效算法&#xff0c;它可以应对包括复杂地形&#xff0c;各种尺度的障碍物以及不同地形的路径规划问题。掌握A星寻路算法能够提高路径规划效率&#xff0c;应对…
阅读更多...
大模型参数高效微调

大模型参数高效微调

参数高效微调目的 PEFT技术旨在通过最小化微调参数的数量和计算复杂度&#xff0c;来提高预训练模型在新任务上的性能&#xff0c;从而缓解大型预训练模型的训练成本。这样一来&#xff0c;即使计算资源受限&#xff0c;也可以利用预训练模型的知识来迅速适应新任务&#xff0…
阅读更多...
域名 SSL 证书信息解析 API 数据接口

域名 SSL 证书信息解析 API 数据接口

域名 SSL 证书信息解析 API 数据接口 网络工具&#xff0c;提供域名 SSL 证书信息解析&#xff0c;多信息查询&#xff0c;毫秒级响应。 1. 产品功能 提供域名 SSL 证书信息解析&#xff1b;最完整 SSL 属性信息解析&#xff1b;支持多种元素信息抽取&#xff0c;包括主题的可…
阅读更多...
【Java程序设计】【C00278】基于Springboot的数码论坛管理系统（有论文）

【Java程序设计】【C00278】基于Springboot的数码论坛管理系统（有论文）

基于Springboot的数码论坛管理系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的数码论坛系统 本系统分为系统功能模块、管理员功能模块以及用户功能模块。 系统功能模块&#xff1a;在系统首页可以查看首页、…
阅读更多...
Linux：Jenkins：GitLab+Maven+Jenkins的部署

Linux：Jenkins：GitLab+Maven+Jenkins的部署

1.环境 我这里准备了三台centos7 1.用于部署gitlab 运行内存&#xff1a;6G 名字&#xff1a;Jenkins-GitLab 192.168.6.1 2.用于部署jenkins 运行内存&#xff1a;2G 名字&#xff1a;Jenkins-server 192.168.6.2 3.用于打包测试…
阅读更多...
全面解析企业财务报表系列之五：阅读财报结构、顺序、模块与不同侧重

全面解析企业财务报表系列之五：阅读财报结构、顺序、模块与不同侧重

全面解析企业财务报表系列之五&#xff1a;阅读财报结构、顺序、模块与不同侧重 一、明确本次报表分析的目的二、确定报表分析的重点项目三、重点分析项目之间的联系四、资产负债表的阅读五、利润表的阅读六、现金流量表的阅读七、综合分析 一、明确本次报表分析的目的 报表的…
阅读更多...
VBA即用型代码手册：立即保护所有工作表Code及插入多工作表Code

VBA即用型代码手册：立即保护所有工作表Code及插入多工作表Code

我给VBA下的定义&#xff1a;VBA是个人小型自动化处理的有效工具。可以大大提高自己的劳动效率&#xff0c;而且可以提高数据的准确性。我这里专注VBA,将我多年的经验汇集在VBA系列九套教程中。 作为我的学员要利用我的积木编程思想&#xff0c;积木编程最重要的是积木如何搭建…
阅读更多...
【C语言】指针变量未初始化

【C语言】指针变量未初始化

我们知道&#xff1a;全局变量未赋初值&#xff0c;编译器会直接赋值为0&#xff1b;局部变量如果未赋初值&#xff0c;则会维持上一状态保存在该地址上的值&#xff0c;这个值是随机的。把这个值赋值给局部变量是没有意义的。 但是指针变量是如何解决不赋初值&#xff1f; 指…
阅读更多...
探索设计模式的魅力：状态模式揭秘-如何优雅地处理复杂状态转换

探索设计模式的魅力：状态模式揭秘-如何优雅地处理复杂状态转换

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;并且坚持默默的做事。 探索设计模式的魅力&#xff1a;状态模式揭秘-如何优雅地处理复杂状态转换 文章目录 一、案例…
阅读更多...
力扣 187. 重复的DNA序列

力扣 187. 重复的DNA序列

1.题目 DNA序列 由一系列核苷酸组成&#xff0c;缩写为 A, C, G 和 T.。 例如&#xff0c;"ACGAATTCCG" 是一个 DNA序列 。 在研究 DNA 时&#xff0c;识别 DNA 中的重复序列非常有用。 给定一个表示 DNA序列 的字符串 s &#xff0c;返回所有在 DNA 分子中出现不止一…
阅读更多...
如何连接ACL认证的Redis

如何连接ACL认证的Redis

点击上方蓝字关注我 应用程序连接开启了ACL认证的Redis时与原先的方式有差别&#xff0c;本文介绍几种连接开启ACL认证的Redis的Redis的方法。 对于RedisACL认证相关内容&#xff0c;可以参考历史文章&#xff1a; Redis权限管理体系(一&#xff09;&#xff1a;客户端名及用户…
阅读更多...
Python之numpy

Python之numpy

目录 安装 ndarray 说明文档 NumPy(Numerical Python) 是 Python 语言的一个扩展程序库&#xff0c;支持大量的维度数组与矩阵运算&#xff0c;此外也针对数组运算提供大量的数学函数库。 安装 pip3 install --user numpy scipy matplotlib ndarray NumP提供了 N 维数组…
阅读更多...
国家之间的竞争绝不仅仅是几个AI软件的竞争

国家之间的竞争绝不仅仅是几个AI软件的竞争

国家之间的竞争应该不仅仅是几个AI软件的竞争&#xff0c;而更多地是人机环境系统生态的竞争。在这种观点下&#xff0c;国家之间的竞争被视为一个更为复杂和综合的竞争过程&#xff0c;涉及到人类、技术系统以及周围环境的综合作用。 在人机环境系统生态的竞争中&#xff0c;人…
阅读更多...
Stable Diffusion 3正式发布，旨在巩固其在AI图像领域相对于Sora和Gemini的领先地位

Stable Diffusion 3正式发布，旨在巩固其在AI图像领域相对于Sora和Gemini的领先地位

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
Selenium浏览器自动化测试框架详解

Selenium浏览器自动化测试框架详解

selenium简介 介绍 Selenium [1] 是一个用于Web应用程序测试的工具。Selenium测试直接运行在浏览器中&#xff0c;就像真正的用户在操作一样。支持的浏览器包括IE&#xff08;7, 8, 9, 10, 11&#xff09;&#xff0c;Mozilla Firefox&#xff0c;Safari&#xff0c;Google C…
阅读更多...
最新文章

Copyright @ 2022~2023