题目描述
Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。但是Frank发现，由于很多书的宽度不同，所以书看起来还是非常不整齐。于是他决定从中拿掉k本书，使得书架可以看起来整齐一点。
书架的不整齐度是这样定义的：每两本书宽度的差的绝对值的和。例如有4本书：
1×21 \times 21×2
5×35 \times 35×3
2×42 \times 42×4
3×13 \times 13×1
那么Frank将其排列整齐后是：
1×21 \times 21×2
2×42 \times 42×4
3×13 \times 13×1
5×35 \times 35×3
不整齐度就是2+3+2=72+3+2=72+3+2=7
已知每本书的高度都不一样，请你求出去掉k本书后的最小的不整齐度。
输入输出格式
输入格式：
第一行两个数字nnn和kkk，代表书有几本，从中去掉几本。(1≤n≤100,1≤k<n1 \le n \le 100, 1 \le k<n1≤n≤100,1≤k<n)
下面的nnn行，每行两个数字表示一本书的高度和宽度，均小于200200200。
保证高度不重复
输出格式：
一行一个整数，表示书架的最小不整齐度。
输入输出样例
输入样例#1： 复制
4 1
1 2
2 4
3 1
5 3
输出样例#1： 复制
3 这个是一个dp，这个应该可以不是特别难的判断出来，但是这个定义不是很好去定义，我又没有想出来，最后看题解定义的
dp数组定义为前i本书选了j本书，且i为最后结束的那本书，然后之后的转移就比较好转移，就往下一本书要不要，
要的话是接在那个之后最好，所以这里有三重循环，我虽然意识到了，但是呢，没有写出来，最后还是借助题解写完的，
这个要注意的就是有些前i个选不出j个，因为可能i<j。注意一下这里就好了。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 110;
int dp[maxn][maxn];//表示从前面i本书中选j本，且以第i本为结束的最小整齐度。
struct node
{
int h, d;
}exa[maxn]; bool cmp(node a, node b)
{
return a.h < b.h;
} int main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &exa[i].h, &exa[i].d);
}
sort(exa + 1,exa + 1 + n, cmp);
for (int i = 0; i <= n; i++)
{
dp[i][1] = 0;
}
for (int i = 1; i <= n; i++)
{
for (int j = 2; j <= min(n-k,i); j++)
{
dp[i][j] = inf;
for (int k = j-1; k <=i-1 ; k++)
{
dp[i][j] = min(dp[k][j - 1] + abs(exa[i].d - exa[k].d), dp[i][j]);
}
}
}
int ans = inf;
for (int i = n-k; i <= n; i++) ans = min(dp[i][n - k], ans);
printf("%d\n", ans);
return 0;
}