hdu 1421 搬寝室 （DP）

点击打开链接

题目意思：

给你一个n和n个数，从中选出k个，使疲劳最小。。

疲劳计算方法：（两手物品质量差的平方）。

分析：先进行排序，只有当拿相邻的两个物品时，才有可能最小。。

典型的DP： dp[ i ] [ j ]=min( dp[ i -1] [  j ] , dp[ i-2 ] [ j-1]+a[i-1]);

dp[i][j]表示：从i个物品中拿j个的最小疲劳值。。

#include"stdio.h"
#include"string.h"
#include"algorithm"
#define MIN(a,b) a>b?b:a;
int dp[2001][1001];
int main()
{
	int n,k,i,j,a[2001];
	while(scanf("%d%d",&n,&k)!=-1)
	{
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		//采用C++的一个排序方法。。
		std::sort(a+1,a+1+n);
		for(i=1;i<n;i++)
			a[i]=(a[i]-a[i+1])*(a[i]-a[i+1]);
		memset(dp,127,sizeof(dp));
		for(i=0;i<=n;i++)dp[i][0]=0;
		for(i=2;i<=n;i++)
		{
			for(j=1;2*j<=i;j++)
				dp[i][j]=MIN(dp[i-1][j],dp[i-2][j-1]+a[i-1]);
		}
		printf("%d\n",dp[n][k]);
	}
	return 0;
}