P1103 书本整理

    • 1.1K通过
    • 2.4K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架,想要把书放在书架上。书架可以放下所有的书,所以Frank首先将书按高度顺序排列在书架上。但是Frank发现,由于很多书的宽度不同,所以书看起来还是非常不整齐。于是他决定从中拿掉k本书,使得书架可以看起来整齐一点。

    书架的不整齐度是这样定义的:每两本书宽度的差的绝对值的和。例如有4本书:

    $1 \times 2$
    $5 \times 3$
    $2 \times 4$
    $3 \times 1$
    那么Frank将其排列整齐后是:

    $1 \times 2$
    $2 \times 4$
    $3 \times 1$
    $5 \times 3$
    不整齐度就是 $2+3+2=7$

    已知每本书的高度都不一样,请你求出去掉k本书后的最小的不整齐度。

    输入输出格式

    输入格式:

    第一行两个数字 $n$ 和 $k$ ,代表书有几本,从中去掉几本。( $1 \le n \le 100, 1 \le k<n$ )

    下面的 $n$ 行,每行两个数字表示一本书的高度和宽度,均小于 $200$ 。

    保证高度不重复

    输出格式:

    一行一个整数,表示书架的最小不整齐度。

    输入输出样例

    输入样例#1: 复制
    4 1
    1 2
    2 4
    3 1
    5 3
    
    输出样例#1: 复制
    3
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。