P1103 书本整理

题目描述

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

样例输入 #1

4 1
1 2
2 4
3 1
5 3

样例输出 #1

3

/* * @Description: To iterate is human, to recurse divine. * @Autor: Recursion * @Date: 2022-08-04 19:24:40 * @LastEditTime: 2022-08-04 21:00:34 */
#include <bits/stdc++.h>
#define LL long long 
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e9 + 10;
const int N = 1e3+7;
int dp[N][N];
//f[i][j]：以i作末尾，选了j本书时的最小花费
struct node{
    
    int w;
    int h;
}a[N];
bool cmp(node x,node y){
    
    if(x.h<y.h)
        return true;
    return false;
}
int n ,m;
int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(dp,INF,sizeof(dp));
    cin >> n >> m;
    m = n - m;
    for(int i = 1;i <= n;i ++)
        cin >> a[i].h >> a[i].w;
    
    sort(a + 1,a + 1 + n,cmp);

    for(int i = 1;i <= n;i ++)
        dp[i][1] = 0;
    
    for(int i = 2;i <= n;i ++)
        for(int j = 1;j <= i - 1;j ++)
            for(int l = 2;l <= min(i,m);l++)
                dp[i][l] = min(dp[i][l],dp[j][l - 1] + abs(a[i].w - a[j].w));
    int ans = INF;
    for(int i = m;i <= n;i ++)
        ans = min(ans,dp[i][m]);
    cout << ans << endl;
    return 0;
}