搬寢室
Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18191????Accepted Submission(s): 6170
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
1 /* 2 dp(i,j)表示：i個數內,選出j對數的最優策略 3 dp(i,j)=max(dp(i-1,j),dp(i-2,j-1)+(a[i]-a[i-1])^2) 4 */ 5 #include <iostream> 6 #include <cstdio> 7 #include <cstring> 8 using namespace std; 9 10 typedef __int64 LL; 11 const LL INF=1e15; 12 const int maxn=2005; 13 int a[maxn]; 14 LL dp[maxn][maxn]; 15 inline LL min(LL a,LL b){return a<b?a:b;} 16 17 void quicksort(int l,int r) 18 { 19 if(l<r) 20 { 21 int t=a[l],i=l,j=r; 22 while(i!=j) 23 { 24 while(a[j]>=t && i<j) j--; 25 while(a[i]<=t && i<j) i++; 26 if(i<j) swap(a[i],a[j]); 27 } 28 a[l]=a[i];a[i]=t; 29 quicksort(l,i-1); 30 quicksort(i+1,r); 31 } 32 } 33 34 int main() 35 { 36 int n,k,i,j; 37 while(~scanf("%d%d",&n,&k)) 38 { 39 for(i=1;i<=n;i++) scanf("%d",a+i); 40 quicksort(1,n); 41 for(i=0;i<=n;i++) 42 for(j=0;j<=k;j++) 43 dp[i][j]=INF; 44 for(i=0;i<=n;i++) dp[i][0]=0; 45 for(i=2;i<=n;i++) 46 { 47 for(j=1;j<=k && j*2<=i;j++) 48 dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1])); 49 } 50 printf("%I64d\n",dp[n][k]); 51 } 52 return 0; 53 }
?
?
Author
xhd
?
