网站排名突然消失,怎么利用网络挣钱,wordpress原图对比插件,广州艾迪网站建设作者推荐
【广度优先搜索】【网格】【割点】【 推荐】1263. 推箱子
本文涉及知识点
动态规划汇总
LCP04 覆盖
你有一块棋盘#xff0c;棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌#xff0c;你想把这些骨牌不重叠地覆盖在完好的格子上#xff0…作者推荐
【广度优先搜索】【网格】【割点】【 推荐】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的最大值。
代码
核心代码
templateclass 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));}}templateclass Tint bitcount(T x) {int countx 0;while (x) {countx;x (x - 1);}return countx;}vectorint m_vCnt;
};class CEnumMask2
{
public:CEnumMask2(int iMaskCount):m_iMaskCount(iMaskCount){}templateclass GetMask2,class Onvoid 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, vectorvectorint broken) {const int iMaskCount 1 m;vectorint vCan(n, iMaskCount-1);for (const auto v : broken){vCan[v[0]] ^ (1 v[1]);} CBitCounts bitCnt(iMaskCount);vectorint 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];}}vectorint pre(iMaskCount, -100);pre[0] 0;CEnumMask2 enumMask(iMaskCount);for (int r 0; r n; r){vectorint 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]); });vectorint 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());}
};测试用例 templateclass T,class T2
void Assert(const T t1, const T2 t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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;vectorvectorint 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);}}优化
枚举所有合法状态再枚举竖放状态。不用枚举前一行的状态。竖放的状态就是前一行状态。
templateclass 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));}}templateclass Tint bitcount(T x) {int countx 0;while (x) {countx;x (x - 1);}return countx;}vectorint m_vCnt;
};class Solution {
public:int domino(int n, int m, vectorvectorint broken) {const int iMaskCount 1 m;vectorint vCan(n, iMaskCount-1);for (const auto v : broken){vCan[v[0]] ^ (1 v[1]);} CBitCounts bitCnt(iMaskCount);vectorint 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]);}vectorint pre(iMaskCount, -100);pre[0] 0;for (int r 0; r n; r){vectorint 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, vectorvector 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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
