C++前缀和算法:合并石头的最低成本原理、源码及测试用例(二)

简介: C++前缀和算法:合并石头的最低成本原理、源码及测试用例

旧版代码

template<class T>
 void MinSelf(T* seft, const T& other)
 {
   *seft = min(*seft, other);
 }
class Solution {
 public:
   int mergeStones(vector<int>& stones, int k) {
     m_k = k;
     m_c = stones.size();
     m_dp.assign(m_c + 1, vector<vector<int>>(m_c, vector<int>(k + 1, 1000 * 1000 * 100)));
     vector<int> vPreSum(1);
     for (const auto& stone : stones)
     {
       vPreSum.push_back(vPreSum.back() + stone);
     }
     for (int pos = 0; pos + 1 - 1 < m_c; pos++)
     {
       m_dp[1][pos][1] = 0;
     }
     for (int len = 2; len <= m_c; len++)
     {
       for (int pos = 0; pos+len <= m_c; pos++)
       {
         //int iEnd = pos + len - 1;
         for (int iHeapNum = 2; iHeapNum <= k; iHeapNum++)
         {
           for (int iPreLen = 1; iPreLen < len; iPreLen += k - 1)
           {
             MinSelf(&m_dp[len][pos][iHeapNum], m_dp[iPreLen][pos][1] + m_dp[len - iPreLen][pos + iPreLen][iHeapNum - 1]);
           }
         }
         m_dp[len][pos][1] = m_dp[len][pos][k] + vPreSum[pos + len] - vPreSum[pos];
       }      
     }    
     return (m_dp[m_c][0][1] >= 1000 * 1000 * 100) ? -1 : m_dp[m_c][0][1];
   }
   int m_k;
   int m_c;
   vector<vector<vector<int>>> m_dp;
 };

旧版代码2

template<class T>
 void MinSelf(T* seft, const T& other)
 {
   *seft = min(*seft, other);
 }
 class Solution {
 public:
   int mergeStones(vector<int>& stones, int k) {
     m_k = k;
     m_c = stones.size();
     m_dp.assign(m_c + 1, vector<int>(m_c, ( 1000 * 1000 * 100)));
     if ((m_c-1) % (k - 1) != 0)
     {
       return -1;
     }
     vector<int> vPreSum(1);
     for (const auto& stone : stones)
     {
       vPreSum.push_back(vPreSum.back() + stone);
     }
     for (int pos = 0; pos + 1 - 1 < m_c; pos++)
     {
       m_dp[1][pos] = 0;
     }
     for (int len = 2; len <= m_c; len++)
     {
       for (int pos = 0; pos+len <= m_c; pos++)
       {
         for (int iPreLen = 1; iPreLen < len; iPreLen += k - 1)
         {
           MinSelf(&m_dp[len][pos], m_dp[iPreLen][pos] + m_dp[len - iPreLen][pos + iPreLen]);
         }
         if ((len-1) % (k - 1) == 0)
         {
           m_dp[len][pos] +=  vPreSum[pos + len] - vPreSum[pos];
         }
       }      
     }    
     return (m_dp[m_c][0] >= 1000 * 1000 * 100) ? -1 : m_dp[m_c][0];
   }
   int m_k;
   int m_c;
   vector<vector<int>> m_dp;
 };

旧版代码三

class Solution {
public:
int mergeStones(vector& stones, int k) {
m_c = stones.size();
if (0 != (m_c - 1) % (k-1))
{
return -1;
}
vector vPreSum(1);
for (const auto& n : stones)
{
vPreSum.emplace_back(vPreSum.back() + n);
}
vector<vector> vLenBegin(m_c + 1, vector(m_c));
for (int len = k; len <= m_c; len++)
{
for (int begin = 0; begin + len - 1 < m_c; begin++)
{
int iMaxPreScore = INT_MAX;
for (int lLen = 1; lLen < len; lLen += (k - 1))
{
int rLen = len - lLen;
iMaxPreScore = min(iMaxPreScore, vLenBegin[lLen][begin] + vLenBegin[rLen][begin + lLen]);
}
if (0 == (len - 1) % (k - 1))
{
iMaxPreScore += vPreSum[begin + len] - vPreSum[begin];
}
vLenBegin[len][begin] = iMaxPreScore ;
}
}
return vLenBegin.back().front();
}
int m_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

相关文章
|
21小时前
|
算法 C++
c++算法学习笔记 (5)前缀和+差分
c++算法学习笔记 (5)前缀和+差分
|
3天前
|
人工智能 算法 BI
【算法基础】基础算法(二)--(高精度、前缀和、差分)(下)
【算法基础】基础算法(二)--(高精度、前缀和、差分)(下)
|
3天前
|
存储 算法 索引
【算法基础】基础算法(二)--(高精度、前缀和、差分)(上)
【算法基础】基础算法(二)--(高精度、前缀和、差分)(上)
|
8天前
|
NoSQL 算法 Java
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
|
9天前
|
设计模式 算法 Java
[设计模式Java实现附plantuml源码~行为型]定义算法的框架——模板方法模式
[设计模式Java实现附plantuml源码~行为型]定义算法的框架——模板方法模式
|
9天前
|
算法 C#
winform车牌识别源码(纯算法)
使用C#和Winform开发的纯算法车牌识别系统,无需依赖外部框架。通过去雾、灰度化、均衡化、中值滤波等步骤实现车牌定位和识别。包含详细步骤及源码,适合学习研究。演示视频:[BV1yq4y1a7cb](https://www.bilibili.com/video/BV1yq4y1a7cb/?spm_id_from=333.337.search-card.all.click&vd_source=6d6d1b4c92d36f8d9ca8a23a286bae20)。
|
9天前
|
机器学习/深度学习 算法
【优选算法专栏】专题四:前缀和(二)
【优选算法专栏】专题四:前缀和(二)
23 1
|
9天前
|
算法 vr&ar Perl
【优选算法专栏】专题四:前缀和(一)
【优选算法专栏】专题四:前缀和(一)
26 0
|
9天前
|
人工智能 算法
基础算法--前缀和与差分
基础算法--前缀和与差分
|
9天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。