九度教程第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]);
}
}
补充：软件开发 , C++ ,
