3.5 搬家

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

搬家有多辛苦，相信你们早有耳闻。由于市区建设的需要，继小明之后，小八也加入了这个行列。现在的小八就陷入了极度的纠结之中，看着家里的\(n\)件家具，小八开始发呆，因为\(n\)是一个小于 2000 的整数，实在是太多了，于是小八决定随便搬\(2\times k\)件家具就行了。但还是会很累，因为\(2\times k\)也不小是一个不大于\(n\)的整数。

幸运的是小八有了上次帮小明搬东西的经验，发现每搬一次的疲劳度是左右手的物品的重量差的平方（这里补充一句，小明每次搬两件东西，左手一件右手一件）。例如小八左手拿重量为 3 的物品，右手拿重量为 6 的物品，则他搬完这次的疲劳度为\((6-3)^2= 9\)。现在可怜的小八希望知道搬完这\(2\times k\)件物品后的最佳状态是怎样的（也就是最低的疲劳度），请告诉他吧。

你的任务是从给定的\(n\)件家具中，替小八挑选\(2\times k\)件家具，并规划小八的搬运方案，使得小八最终的疲劳度最低。

数据输入

输入数据有两行,第一行有两个数\(n,k\ (2\leq 2\times k\leq n<2000)\)。第二行有\(n\)个整数分别表示\(n\)件物品的重量（重量是一个小于\(2^{15}\)的正整数）。

数据输出

输出只有一行，表示最低的疲劳度。

输入示例 输出示例
2 1
1 3		 4

源代码

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
33
34
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define ll __int64
#define maxn 2005

ll data[maxn];
ll dp[3][maxn];

inline ll min(ll a, ll b){ return a < b ? a : b; }

int main(){
    int i, j, n, k;
    scanf("%d%d", &n, &k);
    memset(dp, 0x3f, sizeof(dp));
    for (i = 0; i < n; ++i)
        scanf("%I64d", &data[i]);
    sort(data, data + n);
    for (i = 0; i < 3; ++i)dp[i][0] = 0;
    int i_0, i_1, i_2;
    for (i = 1; i < n; ++i){
        i_0 = i % 3;
        i_1 = (i - 1) % 3;
        //+3避免溢出，这样不用单独判断i=2 的情况，多一次无意义的比较而已
        i_2 = (i - 2 + 3) % 3;
        for (j = 1; j <= k; ++j){
            ll x = data[i]-data[i-1];
            dp[i_0][j] = min(dp[i_1][j], dp[i_2][j - 1] + x*x);
        }
    }
    printf("%I64d\n", dp[i_0][k]);
    return 0;
}

设计思路与复杂度分析

重量余越接近的相差越小，所以一定是相邻的两个物品一起搬运。那么先将物品按重量排序之后即可由状态转移方程\(dp(i,j)=min(dp(i-1,j),dp(i-2,j-1)+(w_i-w_{i-1})^2)\)求解。复杂度\(O(n\times k)\)。 可以看到当前的状态只与前两个状态有关，所以可以使用滚动数组节约内存。

0%