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],即处理完所有元素后,最大值不超过最大的离散化值时的最小调整成本。
  • 通过这种方法,我们能够高效地找到满足非递减条件的最优调整方案,同时控制调整成本的上升。

    上一篇:New Year and Domino
    下一篇:Mashmokh and ACM

    发表评论

    最新留言

    表示我来过!
    [***.240.166.169]2025年04月28日 03时16分06秒

    关于作者

        喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
    -- 愿君每日到此一游!

    推荐文章