题目描述：

    给出n个数，从中找出k对数使得每对数差的平方之和最小。

题面建模：

    dp。

    设定dp[i][j]存储的值为当选择到第i个数时，已选出j对数的最小差的平方。

    那么有转移方程dp[i][j]=Min(dp[i-1][j],dp[i-2][j-1]+(object[i]-object[i-1])*(object[i]-object[i-1]))

    这样最后的答案为dp[n][k]。

解题要点：

    注意边界的处理和dp数组的初始化，开始的时候应将dp[i][j]=INF。

时空开销分析：

    空间复杂度：O(n)。

    时间复杂度：O(n^2)。

特别说明：

   无。

程序：

 

#include 
     
      #include 
      
       #include 
       
        #define INF (1<<30)int object[2010];int dp[3][1010];int cmp(const void *a,const void *b){    return *((int*)a)-*((int*)b);}int Min(int a,int b){    return a>b?b:a;}int main(){    int n,k,i,j;    while(scanf("%d %d",&n,&k)!=EOF)    {        for(i=1;i<=n;i++)             scanf("%d",object+i);        qsort(object+1,n,sizeof(object[0]),cmp);        memset(dp,0,sizeof(dp));        for(i=0;i<3;i++)            for(j=1;j<=k;j++)                dp[i][j]=INF;        for(i=1;i<=n;i++)            for(j=1;j<=(i>>1)&&j<=k;j++)                dp[i%3][j]=Min(dp[(i-1)%3][j],dp[(i-2)%3][j-1]+(object[i]-object[i-1])*(object[i]-object[i-1]));        printf("%d\n",dp[n%3][k]);    }    return 1;}