题目描述
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;
- }
来源: http://www.bubuko.com/infodetail-2984183.html