1 /*
2 Author: Leo.W
3 Descriptipn: 一系列的n件物件,只能搬2*k件,且疲劳度为每次搬得两件物品的质量差的平方,求最小疲劳度
4 How to Do: DP动态规划,状态转移类似背包问题,先把所有物品排序,再将相邻物品平方差求出。
5 */
6 #include <iostream>
7 #include <string.h>
8 #include <algorithm>
9 using namespace std;
10 #define min(a,b) (a)<(b)?(a):(b)
11 int d[2001];
12 int dp[2002][1001];
13 int main(){
14 //freopen("in.txt","r",stdin);
15 int n,k;
16 while (scanf("%d%d",&n,&k)!=EOF){
17 int i,j;
18 for(i=1;i<=n;i++) scanf("%d",&d[i]);
19 sort(d+1,d+n+1);
20 for(i=1;i<=n-1;i++) d[i]=(d[i]-d[i+1])*(d[i]-d[i+1]);
21 memset(dp,127,sizeof(dp));
22 for(i=0;i<=n;i++)
23 dp[i][0]=0;
24 for(i=2;i<=n;i++){
25 for(j=1;j*2<=i;j++){//关键代码 注意不要重复 所以只能采用二维
26 dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+d[i-1]);
27 }
28 }
29 printf("%d\n",dp[n][k]);
30 }
31 return 0;
32 }
33
posted on 2012-03-13 17:44
Leo.W 阅读(254)
评论(0) 编辑 收藏 引用