【动态规划】【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包括所有符合以下条件的元素{aj _jj,bj _jj},aj _jj<=bj _jj含义是前 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≡ \equiva1+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];

}

};


目录
打赏
0
0
0
0
36
分享
相关文章
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
22 12
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
27 15
|
30天前
|
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
50 5
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
52 19
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
65 4
|
3月前
|
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
81 2
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
90 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等