书本整理
题目描述
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
解析
对高度进行排序后,高度就没用了,只需要对宽度进行分析。
题目中要求删去k本书,我们可以从反面考虑,即保留多少本书。
设\(dp_{i,j}\)表示枚举到第i本书(且第i本书必须保留)保留了j本书的最小不整齐度,从保留了j-1本书的状态进行转移,即\(dp_{i,j}=min(dp_{t,j-1}+|a[i]-a[t]|)\),其中i从1枚举到n,因为i必须保留,所以j从1开始枚举到min(i,n-k),t从j-1枚举到i-1,最后统计答案即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, k, dp[N][N], b[N];
struct node {
int x, y;
bool operator < (const node b) const {
return x < b.x;
}
}a[N];
int main() {
ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++) b[i] = a[i].y;
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i <= n; i ++) dp[i][1] = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= min(i, n - k); j ++)
for (int t = j - 1; t < i; t ++)
dp[i][j] = min(dp[i][j], dp[t][j - 1] + abs(b[i] - b[t]));
int ans = INT_MAX;
for (int i = n - k; i <= n; i ++) ans = min(ans, dp[i][n - k]);
cout << ans << '\n';
return 0;
}
标签:本书,P1103,书架,int,整齐,times,dp,书本,DP
From: https://www.cnblogs.com/YHxo/p/16857704.html