【动态规划】【C++算法】956 最高的广告牌

这篇具有很好参考价值的文章主要介绍了【动态规划】【C++算法】956 最高的广告牌。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

作者推荐

【动态规划】【map】【C++算法】1289. 下降路径最小和 II

本文涉及知识点

动态规划汇总

956. 最高的广告牌

你正在安装一个广告牌,并希望它高度最大。这块广告牌将有两个钢制支架,两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。举个例子,如果钢筋的长度为 1、2 和 3,则可以将它们焊接在一起形成长度为 6 的支架。
返回 广告牌的最大可能安装高度 。如果没法安装广告牌,请返回 0 。
示例 1:
输入:[1,2,3,6]
输出:6
解释:我们有两个不相交的子集 {1,2,3} 和 {6},它们具有相同的和 sum = 6。
示例 2:
输入:[1,2,3,4,5,6]
输出:10
解释:我们有两个不相交的子集 {2,3,5} 和 {4,6},它们具有相同的和 sum = 10。
示例 3:
输入:[1,2]
输出:0
解释:没法安装广告牌,所以返回 0。
提示:
0 <= rods.length <= 20
1 <= rods[i] <= 1000
sum(rods[i]) <= 5000

动态规划

动态规划的状态表示

朴素方案:pre包括所有符合以下条件的元素{a j _j j,b j _j j},a j _j j<=b j _j j含义是前 i个钢筋可能组成的支架组合。可能的状态数:106
优化方案:假设一b1-a1等于b2-a2,且a1<a2,则a1被淘汰。假定{a1,b1}能够组成的支架高度是n。则第一个剩余支架高度是:c=n-a1,第二个剩余支架高度是d=n-b1 。我们假定a2和c结果,b2和d结合,则第一个支架高度是: n-a1+a2 ,则第二个支架是:n-b1+b2。我们来证明两者相等。即 n-a1+a2 ≡ \equiv n-b1+b2 → \rightarrow 左右加上 a 1 + b 1 − n ‾ → \underline{左右加上a1+b1-n}_\rightarrow 左右加上a1+b1n b1+a2 ≡ \equiv a1+b2 左右减去 a 1 + a 2 ‾ → \underline{左右减去a1+a2}_\rightarrow 左右减去a1+a2 b1-a1 ≡ \equiv b2-a2就是假设一 → \rightarrow 如果a1,b1有解,则a2,b2也有解。而a1+c<a2+c,故a1,b1被淘汰。
pre[j]表示前 i个钢筋可能组成的支架组合中,两根支架的高度差为j,短支架的最大长度。j的取值范围[0,sum(rods[i]) /2]
dp表示前i+1个钢筋的组合。

动态规划的转移方程

每个钢架有三种可能:一,不使用。二,焊在短支架上。三,焊在长支架上。

动态规划的初始状态

pre[0]=0,其它为-10000,表示非法状态。

动态规划的填表顺序

任意顺序处理钢筋。

动态规划的返回值

pre[0],如果是负数,返回0。

代码

核心代码

class Solution {
public:
	int tallestBillboard(vector<int>& rods) {
		const int n = accumulate(rods.begin(), rods.end(), 0)/2;
		vector<int> pre(n+1, -10000);
		pre[0] = 0;
		for (const auto& rod : rods)
		{
			auto dp = pre;//本钢筋不使用
			auto Add = [&](int i1, int i2)
			{
				if (i2 < i1)
				{
					swap(i1, i2);
				}
				if (i2 - i1 > n)
				{
					return;
				}
				dp[i2 - i1] = max(dp[i2 - i1], i1);
			};
			for (int iPre = 0; iPre <= n; iPre++)
			{
				const int i2 = iPre + pre[iPre];
				Add(pre[iPre] + rod, i2);
				Add(pre[iPre], i2 + rod);
			}
			pre.swap(dp);
		}
		return max(0, pre.front());
	}
};

核心代码

template<class T>
void Assert(const T& t1, const T& 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()
{	
	vector<int> rods;
	{
		Solution sln;
		rods = { 1, 2, 3, 6 };
		auto res = sln.tallestBillboard(rods);
		Assert(res,6);
	}

	{
		Solution sln;
		rods = { 1,2,3,4,5,6 };
		auto res = sln.tallestBillboard(rods);
		Assert(res, 10);
	}

	{
		Solution sln;
		rods = { 1,2 };
		auto res = sln.tallestBillboard(rods);
		Assert(res, 0);
	}
	


}

2023年一月

class Solution {
public:
int tallestBillboard(vector& rods) {
//key: 第一个钢筋的长度- 第二根钢筋的长度, value = 第二根钢筋的长度
std::unordered_map<int, int> mPreSubLen;
mPreSubLen[0] = 0;
for (const auto& idata : rods)
{
std::unordered_map<int, int> dp = mPreSubLen;
for (const auto& pre : mPreSubLen )
{
Add(dp, pre.first + idata, pre.second);
Add(dp, pre.first - idata, pre.second + idata);
}
mPreSubLen.swap(dp);
}
return mPreSubLen[0];
}
void Add(std::unordered_map<int, int>& dp,int iSub,int iLen)
{
auto it = dp.find(iSub);
if (dp.end() == it)
{
dp[iSub] = iLen;
}
else
{
it->second = max(it->second, iLen);
}
}
};

2023年8月

class Solution {
public:
int tallestBillboard(vector& rods) {
std::unordered_map<int, int> mDiffToMin;
for (const auto& n : rods)
{
std::unordered_map<int, int> cur = mDiffToMin;
auto AddNew = [&cur](const int& iDiff, const int& iMin)
{
if ((!cur.count(iDiff)) || (iMin > cur[iDiff]))
{
cur[iDiff] = iMin;
}
};
AddNew(n, 0);
for (const auto& [pre, iMin] : mDiffToMin)
{
AddNew(pre + n, iMin);
AddNew(max(pre+iMin, n + iMin) - min(pre + iMin, n + iMin), min(pre + iMin, n + iMin));
}
cur.swap(mDiffToMin);
}
return mDiffToMin[0];
}
};

【动态规划】【C++算法】956 最高的广告牌,# 算法题,算法,动态规划,c++,力扣,广告牌,高度,支架

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。

【动态规划】【C++算法】956 最高的广告牌,# 算法题,算法,动态规划,c++,力扣,广告牌,高度,支架文章来源地址https://www.toymoban.com/news/detail-829697.html

到了这里,关于【动态规划】【C++算法】956 最高的广告牌的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 使用74HC595完成16*16led矩阵广告牌(51单片机软件仿真)

    目录 74HC595简介(个人理解)与模块代码 软件仿真和代码  SHCP是写入595芯片数据的配置 STCP是发送595芯片内信息的配置 DS是数据配置的区域 595芯片有9个输出引脚,最后一个是供给下一块串联的595使用的,下一块串联的595stcp和shcp与上一块连接的引脚一致,下一块的DS与上一块

    2024年02月06日
    浏览(51)
  • web3d-three.js场景设计器-sprite广告牌

    three.js使用Sprite精灵实现文字或者图片广告牌 1.将文字绘制到Canvas,调整对应宽高。 2.作为Cavans材质绑定到Sprite 3.加载到场景调整适当的scale function createLabel({ text, fontSize, textColor, color, imageUrl }) {     return new Promise((resolve, reject) = {         let canvas = document.createElement(\\\'canvas\\\')

    2024年02月02日
    浏览(51)
  • 如果这都不是爱!谷歌承包广告牌喊话苹果;亚马逊裁员的业内分析;李玟VR演唱会明日上线;AMD发布会全程高能;GitHub今日热榜 | ShowMeAI资讯日报

    一线消息,Google 在拉斯维加斯 Harmon Corner 投放了大型新年主题广告,喊话说服苹果采用 RCS 消息协议, 不要在修复像素化的照片和视频上掉链子 。视频显示,在简短的问候信息后,广告牌滚动播放 RCS 代码,并在最后呼吁大家 Help Apple #GetTheMessage 。 Google 早在8月就发起了 G

    2023年04月08日
    浏览(57)
  • 力扣LCR 166. 珠宝的最高价值(java 动态规划)

    Problem: LCR 166. 珠宝的最高价值 改题目与本站64题实质上是一样的,该题目在64题的基础上将求取 最小路径和 改成了求取 最大路径和 。具体实现思路如下: 1.定义一个int类型的二维数组dp大小为给定矩阵frame的行数与列数。该数组用于记录每个当前阶段的 最大路径和 (也是本

    2024年02月01日
    浏览(44)
  • 【算法思维】-- 动态规划(C++)

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间 (中值5*10e8) 。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1

    2024年02月02日
    浏览(45)
  • 【动态规划】C++算法:403.青蛙过河

    视频算法专题 动态规划汇总 一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。 给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过

    2024年01月17日
    浏览(47)
  • 【动态规划】C++算法:最长有效括号

    视频算法专题 动态规划汇总 给你一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 示例 1: 输入:s = “(()” 输出:2 解释:最长有效括号子串是 “()” 示例 2: 输入:s = “)()())” 输出:4 解释:最长有效括号子串是 “()()” 示例

    2024年02月01日
    浏览(56)
  • C++算法 —— 动态规划(2)路径问题

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月06日
    浏览(48)
  • 【动态规划】C++算法312 戳气球

    视频算法专题 动态规划汇总 有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果

    2024年02月03日
    浏览(40)
  • C++算法 —— 动态规划(3)多状态

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月09日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包