最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 问题 S: L13-2 基础2D/1D类动态规划 - 练习10

    正文概述 网友投稿   2026-01-22 16:02:27  

    题目描述

    烛龙战队遇到了一个石柱阵,小极客通过量子分析分析了这个石柱阵,发现石柱阵有个属性——不整齐度。

    想要算出不整齐度,首先要将所有石柱先按照长度从小到大排序,再将每两根石柱宽度差的绝对值进行累加。

    烛龙战队可以在这石柱阵中抽去k根石柱,需要求出抽去石柱后,石柱阵的最小不整齐度。

    石柱阵的不整齐度是这样定义的:每两根石柱宽度的差的绝对值的和。例如有4根石柱:

    1×2(长*宽)

    5×3

    2×4

    3×1

    那么小机器人将其排列整齐后是:

    1×2

    2×4

    3×1

    5×3

    不整齐度就是2+3+2=7

    烛龙战队需要算出这个石柱阵的最小不整齐度。

    输入

    输入包括若干行。 第一行包含两个整数n和k(k

    输出

    输出包括一行,代表最小的不整齐度。

    样例输入

    4 2
    1 2
    5 3
    2 4
    3 1

    样例输出

    1
    信息学奥赛网,一个优质的源码资源平台!
    信息学奥赛网 » 问题 S: L13-2 基础2D/1D类动态规划 - 练习10