九度教程第99題

C語言源碼： [cpp]  #include<stdio.h>   #include<stdlib.h>   int a[2005],dp[2005][2005];   int m(int a,int b)   {       return a>b?b:a;   }   int cmp(const void *a,const void *b)   {       return *(int *)b-*(int *)a;   }   int main()   {       int n,k,i,j;       while(scanf("%d %d",&n,&k)!=EOF)       {           for(i=1;i<=n;i++)               scanf("%d",&a[i]);           qsort(&a[1],n,sizeof(a[1]),cmp);           for(i=0;i<=n;i++)               for(j=0;j<=n;j++)                   dp[i][j]=0;           for(i=2;i<=n;i++)           {               for(j=1;j<=i/2;j++)               {                   if(i==j*2)                       dp[i][j]=dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]);                   else                       dp[i][j]=m(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));               }           }           printf("%d\n",dp[n][k]);       }   }