随笔-65  评论-6  文章-0  trackbacks-0
 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 阅读(246) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理