這道題我真心不會了…… 題意的話按題查詢好了，我就說我求助加上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;
}
|