搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2
k件过去就行了.但还是会很累,因为2
k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2
= 9.现在可怜的xhd希望知道搬完这2
k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.
Input
每组输入数据有两行,第一行有两个数n,k(2<=2
k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).
Output
对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.
Sample Input
2 1
1 3
Sample Output
4
前言：这一题看着就有点懵逼，一点都没有感觉出来这是要用 dp 来做的题，再后来听大佬讲完题后，才恍然大悟，这原来就是一道 稍微复杂一点的 01背包问题，还是自己对背包问题理解不够深刻，留下太菜的眼泪💧。
解题思路
开始之前先解释几个变量的意识
| ar[i] | 首先ar数组使用了存储物品的，ar[i] 就是第 i 件物品 |
|---|---|
| dp[i][j] | 表示在 当前物品为i，已经取了j对物品时候的最小疲劳值为 dp[i][j] |
1.题意：在 n 件物品中 取 k对物品，让求疲劳度最小为多少？
2.思路：对于这种 以“取”字为标志 + 再加上 疲劳度最小（让求最优解） 大部分就是 dp问题了。那么说为什么这个题像01背包问题呢？ 我们可以 2*k 件物品视为背包的容量， 可选的物品件数为 n ，物品的价值就是疲劳度（不过这里让求的是 最下的价值而已），我当时就被这个一次取两件物品，搞蒙了，不知道该怎么做了，
其实我们可以先对 ar[i] 进行排序，这样我们在为了获得最小的疲劳的时候，我们一定是取相邻的两件物品，这样才能产生最小的疲劳值
，然后这一题 与 01 背包问题 在去物品的时候的差异是：对于这一题：对当前物品为 i 的时候要么 不取第i件物品，要么取第 i 件与 i – 1 件物品 ，而对于01背包：要么取第i件物品，要么不取第 i 件物品。明白了这些剩下的就是找状态转移方程（思路如下图）：
⚠️图上的是 j 表示已经取了 j 对物品
举个🌰：
我们 有5 件物品：ar[1 ~ 5] = { 1 , 2 , 3 , 4 , 4} ，假定k = 2 我们要选择2对物品。
我们在初始化dp数组后：
| I / j | 0 | 1 | 2 |
|---|---|---|---|
| ar[0] | 0 | +∞ | +∞ |
| ar[1] | 0 | ∞ | ∞ |
| ar[2] | 0 | ∞ | ∞ |
| ar[3] | 0 | ∞ | ∞ |
| ar[4] | 0 | ∞ | ∞ |
| ar[5] | 0 | ∞ | ∞ |
剩下的就是填表格了：
| I / j | 0 | 1 | 2 |
|---|---|---|---|
| ar[0] | 0 | +∞ | +∞ |
| ar[1] | 0 | ∞ | ∞ |
| ar[2] | 0 | 1 | ∞ |
| ar[3] | 0 | 1 | ∞ |
| ar[4] | 0 | 1 | 2 |
| ar[5] | 0 | 0 |
|
当 i = 0 与 i = 1 的时候没法选择一对物品的时候，
题解如下
#include<iostream>
#include<string.h>
#include<algorithm>
#include<climits>
using namespace std;
const int Len = 2005;
long long int ar[Len];
long long int dp[Len][Len]; //dp[i][j] 表示在 当前物品为i，已经取了j对物品时候的最小疲劳值为 dp[i][j]
int main()
{
freopen("T.txt","r",stdin);
int n,k;
while(scanf("%d %d", &n, &k) != EOF)
{
for(int i = 1; i <= n; i ++)
scanf("%lld", &ar[i]);
//先对ar[]数组进行排序，因为只有相邻两件物品才能产生最小疲劳值
sort(ar + 1 , ar + 1 + n);
//这里因为要取最小疲劳值，所以我们要对dp数组进行特殊的初始化(为什么要这样初始化：因为当 要取的物品件数 j == 0 时疲劳值一定为 0 ，另外因为要去最小疲劳值，所以要把所有dp[0 < i < n][1 < j < k] 设置为无穷大)
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= k; j ++)
j ? dp[i][j] = LONG_LONG_MAX : dp[i][j] = 0;
for(int i = 2; i <= n; i ++) //i从2 开始是因为我们每次选择物品就 一下要选择两件，但我们不选第 i 件物品的时候，那么我们所求的最优值为：dp[i - 1][j] (因为没有选择物品，所以 j 还是 j) ， 但是我们假如，我们选择了第 i 件物品，那么第 i - 1件物品也要被一起选择上 当前的最优为（前 i - 2 件物品，选择 j - 1物品时的疲劳值 + 当前前选择 i 与 i-1两件物品造成的疲劳值 ）：dp[i - 2][j - 1] + (ar[i] - ar[i - 1]) * (ar[i] * ar[i - 1])
for(int j = 1; j <= k && j <= i/2; j ++)
dp[i][j] = min(dp[i - 1][j] , dp[i - 2][j - 1] + (ar[i] - ar[i - 1]) * (ar[i] - ar[i - 1]));
printf("%lld\n",dp[n][k]);
}
return 0;
}