九度教程第99题
题目地址：http://jobdu.sinaapp.com/problem.php?cid=1040&pid=98
C语言源码：
#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]);elsedp[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]);}}