这道题我真心不会了…… 题意的话按题查询好了，我就说我求助加上YY的解题好了…… 当然，看了那个纠结的题意我果断的就被虐到了，额啊，神题啊……给跪…… 首先，既然疲劳度是做差，那排个序好了，有序状态下相邻两个做差是尽量小的。 状 态是dp[i][j]表示在前i个物品中找出j对使得疲劳度最小，有一个决策就是第i个物品用还是不用，如果不用的话，前i个物品的疲劳度一定是等于前 i-1个物品找出j对的疲劳度，如果用了，那用的一定是第i个和第i-1个，那就应该等于前i-2个物品中找出j-1对的最小疲劳度加上这两个物品获得的 疲劳度。状态转移方程：dp[i][i]=min(dp[i-1][j],dp[i-2][j-1]+(w[i]-w[i-1])^2)。然后就写代码好 了…… 特别鸣谢：孟哥silver__bullet   view code
#include <iostream>
#include <algorithm>
#include <cstdio>
#define min(a,b) ((a) < (b) ? (a) : (b))
using namespace std;
int main()
{
long n, k, i, j, w[2005], dp[2005][1005];
cin >> n >> k;
for (i = 1; i <= n; i++) scanf("%ld", &w[i]);
sort(w + 1, w + 1 + n);
for (i = 0; i <= n; i++)
for (j = 0; j <= k; j++) dp[i][j] = 210000000;
for (i = 0; i <= n; i++) dp[i][0] = 0;
for (i = 2; i <= n; i++)
for (j = 1; j <= (i / 2); j++)
dp[i][j] = min(dp[i - 1][j], dp[i - 2][j - 1] + (w[i] - w[i - 1]) * (w[i] - w[i - 1]));
cout << dp[n][k] << endl;
return 0;
}
|