现在的位置: 首页 > 综合 > 正文

hdu1421

2014年01月30日 ⁄ 综合 ⁄ 共 587字 ⁄ 字号 评论关闭
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;

const int MAX=2001;
int s[MAX][MAX/2+1];//表示前i个物品搬j对物品的最小疲劳度.
int a[MAX];

int main(){
	int n,k;
	while(cin>>n>>k){
		for(int i=0;i<n;++i){
			cin>>a[i];
		}
		sort(a,a+n);//对物品重量进行排序 
		for(int j=1;j<=k;++j){
			for(int i=1;i<=n;++i){
				if(2*j<=i){
					//如果前i个物品能搬j对物品           
					s[i][j]=min(s[i-2][j-1]+(a[i-1]-a[i-2])*(a[i-1]-a[i-2]),s[i-1][j]);
				}
				else s[i][j]=INF;//无法搬j对物品就疲劳度设为无穷大 
			}
		}
		cout<<s[n][k]<<endl;
	}
	return 0;
} 

http://acm.hdu.edu.cn/showproblem.php?pid=1421

抱歉!评论已关闭.