自动搬运

查看原文

来自洛谷，原作者为

	学委 希望以后某时候还能来写题！

搬运于2025-08-24 21:20:58，当前版本为作者最后更新于2018-07-04 20:19:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先理解题意

对于给出的书本，Frank会先把它们按照高度排好序，接下来通过删去一些书本来达到宽度最整齐；不论怎么删去，都是在原有顺序的基础上抽走。

为我这种DP初学者的详细分析

（以下的“差”指的是差的绝对值）

“抽走”对于整齐度的影响是很奇怪的：减去自己与两旁书本宽度的差，再加上那两书本宽度的差。尽量转化为已学的模型：从 $n$ 本书里面挑出 $n-k$ 本，按原顺序排列达到宽度最整齐。

这是不是很熟悉？如果不，我们一本本地尝试加入，那么**“当前试着把哪一本加入”就是状态的一个维度**（至少要用 $f[i]$）。一步步推导出状态转移方程。

取第一本，不用花费（花费即增加“不整齐度”）。

第二本书，

①：假如自顾自，成为一长串书本的队首（也就是忽略第一本，从第二本开始取），不用花费。

②：可是如果接上第一本，要花费，好处是队列长度增加到 $2$ 了。发现了吗？队列长度也是某个维度(至少要用 $f[i][l]$)。

到第三本书，

①：如果忽略前两本，不用花费，但是只取了这么一本书。$f[3][1] = 0$。

②：如果从第一本或第二本接上，长度都会变成2，那么我们选择花费小的一种方式。$f[3][2] = min( f[1][1] + abs (a[3].w - a[1].w), f[2][1] + abs(a[3].w - a[2].w) )$。

③：如果前两本都接上，队列成为 $1,2,3$。

尝试加入第四本书，

①：也可以从自己开始取，$f[4][1] = 0$。

②：也可以从 $1$ 或 $2$ 或 $3$ 其中一本接上，长度都会变成 $2$，择优。

③：也可以从长度为 $2$ 的队列接上^，择优。

④：也可以接上 $1,2,3$ 这个长度为 $3$ 的队列。

^此时前三本中花费最小、长度为2的队列已经存储在 $f[2][2]$ 和 $f[3][2]$，为什么不直接用一个 $f[2]$ 存储？因为第四本与 $2,3$ 两本书相邻的代价是不同的。不存在 $f[1][2]$，因为取到第一本的时候没有长度为 $2$ 的队列。

第五本，第六本依此类推。

#include<bits/stdc++.h>
using namespace std;

int n, k, m, Min = 0x7fffffff;
int f[501][501];
//f[i][l]：以i作末尾，选了l本书时的最小花费

struct info
{
	int h, w;
}a[1001];

bool cmp(const info & x, const info & y)
{
	return x.h < y.h;
}

int main()
{
	cin >> n >> k;
	m = n - k;//选取m本书 
	for(int i = 1; i <= n; i++)
		scanf("%d %d", &a[i].h, &a[i].w);
		
	sort(a+1, a+n+1, cmp);//高度决定顺序
	
	memset(f, 20, sizeof(f));//初始极大，能缩小就缩小
	
	for(int i = 1; i <= n; i++)
		f[i][1] = 0;
	//单独选择任何书都不会有花费
	 
	for(int i = 2; i <= n; i++)//试着放第i本的时候 
		for(int j = 1; j <= i-1; j++)//尝试与前面第j本相邻
			for(int l = 2; l <= min(i, m); l++)//放下第i本时，能从之前长1的队列继承为长2的队列，也能从之前长2的队列继承为长3的队列……l表示放下后的长度
            //显然试到第i本时，长度不会超过i，也不会超过m，m是最终需要的长度
				 
				f[i][l] = min(f[i][l], f[j][l-1] + abs(a[i].w - a[j].w/*这是尝试相邻的书本*/));//放第i本继承到长度为l，总花费越小越好
		
	for(int i = m; i <= n; i++)
		Min = min(Min, f[i][m]);//i的循环的意思是：以m结尾的队列，可能最小，以m+1结尾的队列也可能的……以n结尾的队列也可能。
	
	printf("%d\n", Min);
	return 0;
}