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： 复制

输出样例#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;

}

巴特西

dp P1103 书本整理洛谷

题目描述

输入输出格式

输入输出样例

最新文章

热门文章

巴特西

dp P1103 书本整理 洛谷

题目描述

输入输出格式

输入输出样例

最新文章

热门文章

dp P1103 书本整理洛谷