hdu 1421 搬寝室

#include <stdlib.h>
#include <string.h>
#define min(x,y) (x)<(y)?(x):(y)
#define INF 0x7fffffff
int dp[2000][1000];
int w[2000];
int (const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}
int main()
{
    int n,k;
    int i,j;
    while (scanf("%d%d",&n,&k)!=EOF)
    {
        for ( i = 1; i <= n;i++)
            scanf("%d",&w[i]);
        qsort(w+1,n,sizeof(w[1]),cmp);
        for ( i = 0; i <= n; i++)
        {
            dp[i][0] = 0;
            for ( j = 1; j<=k; j++)
                dp[i][j] = INF;
        }
        for ( i = 2; i <= n; i++)
        {
            for (j = 1; j <= i/2 ;j++)  
                dp[i][j] = min(dp[i-1][j],dp[i-2][j-1] + (w[i]-w[i-1])*(w[i]-w[i-1]));
        }
        
            //状态转移：两种情况取较小值  1：从序列前i-1个数中取j个代价 2：从序列前i-2个数中取j-1个的代价加上w[i]和w[的代价
        //w要是排好序的，这样所做的选择必然是相邻的两个数
        printf("%dn",dp[n][k]);
    }
    return 0;
}