dp P1103 书本整理 洛谷

题目描述

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;
}

  


上一篇:Too many connections


下一篇:ios九宫格算法