HDU1421 搬寝室

原题链接:HDU1421

题目大意:共有 $n$ 件物品,需要将其中的 $2k$ 件物品搬走,每搬一次的疲劳度为左右手的物品的重量差的平方,求搬完 $2k$ 件物品的最小疲劳度。

贪心 + DP

将物品重量排序,显然对于每个物品,选择与其相邻的物品组合,能使得该组疲劳度最小。我们只需要从中选出 $k$ 组即可,每组为相邻的物品。

状态表示 $f[i][j]$:从 $1$~$i$ 中选,组成了 $j$ 组的最小疲惫度。

状态计算:

  1. 不选择第 $i$ 个物品与 $i-1$ 这一组,那么继承 $f[i-1][j]$
  2. 选择 $i$ 与 $i-1$ 这一组,则由 $f[i-2][j-1]$ 转移而来,加上与 $i-1$ 这一组即可。

$$ f[i][j] = min(f[i - 1][j], f[i - 2][j - 1] + get(w[i], w[i - 1])); $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 2010;

int n, k;
LL w[N];
LL f[N][N / 2]; // f[i][j]:从1~i中选,组成了j组的最小疲惫度

LL get(LL a, LL b) {
	return (a - b) * (a - b);
}

int main() {   
	while (cin >> n >> k) {
		for (int i = 1; i <= n; i++) cin >> w[i];
		sort(w + 1, w + n + 1);	
		memset(f, 0x3f, sizeof f);
		for (int i = 0; i <= n; i++) f[i][0] = 0;
		for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= k && j <= i / 2; j++)
				f[i][j] = min(f[i - 1][j], f[i - 2][j - 1] + get(w[i], w[i - 1]));
        }
		cout << f[n][k] << endl;
	}
    return 0;
}
updatedupdated2020-05-192020-05-19
加载评论
点击刷新