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.2cto.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.2cto.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; 
}