搬寝室
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13414 Accepted Submission(s): 4533
Problem Description 搬寝室是很累的,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
Author xhd 解題思路： 題目意思為求n個物品，拿k對使得消耗的體力最少，或者說是這k對物品，每一對中兩件物品的品質差平方最小，是以要使得品質差的平方小，隻能排序後取品質相鄰兩個物品作為一對； 現在設f[i][j]為前i件物品組成k對所消耗的體力最小； 這時分兩種情況含有第i件物品和不含有第i件物品（即第i件物品是不是含在第j對裡） 1.含有i件物品 則有 f[i][j]=f[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]); 2.不含第i件物品則有 f[i][j]=f[i-1][j]; 是以動态轉移方程為:f[i][j]=minn(f[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]), f[i][j]=f[i-1][j]); 代碼如下：
#include <stdio.h>
#include <stdlib.h>
#define size 2005
#define INIF 2147483646
int f[size][1005];
int minn(int a,int b)
{
return a<=b?a:b;
}
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;// 從小到大排序
}
int main()
{
int n,k,i,j;
int val[size]={0};
f[0][0]=0;
while(scanf("%d%d",&n,&k)!=EOF)
{
val[0]=0;
for(i=1; i<=n; i++)
scanf("%d",&val[i]);
qsort(val+1,n,sizeof(val[0]),cmp);
for(i=0; i<=n; i++)
for(j=1; j<=k; j++)
f[i][j]=INIF;
for(i=2; i<=n; i++)
for(j=1; j*2<=i; j++)
f[i][j]=minn(f[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]),f[i-1][j]);
printf("%d\n",f[n][k]);
}
return 0;
}