
Making the grade 和Sonya and Problem Wihtout a Legend
发布日期:2021-05-08 16:30:22
浏览次数:12
分类:精选文章
本文共 506 字,大约阅读时间需要 1 分钟。
为了将给定的序列转换为非递减序列并最小化调整成本,我们可以使用离散化和动态规划的方法。以下是详细的步骤说明:
离散化处理:
- 将原序列中的每个元素减去其索引i,得到新的序列b。
- 对b进行排序并去重,得到离散化后的数组b_sorted。
动态规划表的初始化:
- 创建一个二维数组d,其中d[i][j]表示处理前i个元素后,最大值不超过b_sorted[j]时的最小调整成本。
- 初始化d[0][0] = 0,其他d[0][j]为一个很大的值(如INF)。
动态规划表的填充:
- 对于每个i(从1到n),遍历离散化后的每个j(从1到m)。
- 计算将第i个元素调整为b_sorted[j]的成本:cost = d[i-1][j] + |a[i] - b_sorted[j]|
- 如果这个成本小于d[i][j],则更新d[i][j]为cost。
- 另外,比较将第i个元素调整为b_sorted[j-1]的情况,取较小的成本作为d[i][j]。
结果提取:
- 最终答案为d[n][m],即处理完所有元素后,最大值不超过最大的离散化值时的最小调整成本。
通过这种方法,我们能够高效地找到满足非递减条件的最优调整方案,同时控制调整成本的上升。
发表评论
最新留言
表示我来过!
[***.240.166.169]2025年04月28日 03时16分06秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
word文档注入(追踪word文档)未完
2019-03-15
作为我的第一篇csdn博客吧
2019-03-15
java中简单实现栈
2019-03-15
ajax异步提交失败
2019-03-15
一道简单的访问越界、栈溢出pwn解题记录
2019-03-15
ubuntu18.04.4版本安装docker教程
2019-03-15
Stream 某些API
2019-03-15
关于项目中 对Java 的为空判断整理
2019-03-15
测试调用另一台电脑ip是否有用
2019-03-15
mos-excel集成文档
2019-03-15
Tomcat执行流程!
2019-03-15
chat 快问!
2019-03-15
3.jdk的环境配置
2019-03-15
2.连接池
2019-03-15
1.Html
2019-03-15
2.Html与CSS
2019-03-15
3&4.javascript
2019-03-15
5.bootstrap
2019-03-15
6.Xml
2019-03-15