這道題我真心不會(huì)了…… 題意的話按題查詢(xún)好了，我就說(shuō)我求助加上YY的解題好了…… 當(dāng)然，看了那個(gè)糾結(jié)的題意我果斷的就被虐到了，額啊，神題啊……給跪…… 首先，既然疲勞度是做差，那排個(gè)序好了，有序狀態(tài)下相鄰兩個(gè)做差是盡量小的。 狀 態(tài)是dp[i][j]表示在前i個(gè)物品中找出j對(duì)使得疲勞度最小，有一個(gè)決策就是第i個(gè)物品用還是不用，如果不用的話，前i個(gè)物品的疲勞度一定是等于前 i-1個(gè)物品找出j對(duì)的疲勞度，如果用了，那用的一定是第i個(gè)和第i-1個(gè)，那就應(yīng)該等于前i-2個(gè)物品中找出j-1對(duì)的最小疲勞度加上這兩個(gè)物品獲得的 疲勞度。狀態(tài)轉(zhuǎn)移方程：dp[i][i]=min(dp[i-1][j],dp[i-2][j-1]+(w[i]-w[i-1])^2)。然后就寫(xiě)代碼好 了…… 特別鳴謝：孟哥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;
}
|