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个的最小疲劳值。。
www.zzzyk.com
[csharp]
#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++的一个排序方法。。 www.zzzyk.com
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;
}
补充：软件开发 , C++ ,
