1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5  6 int dp[2011][2001]; 7 int a[2011]; 8 int n,k; 9 10 int sqr(int x)11 {12     return x*x;13 }14 15 bool cmp(const int a,const int b)16 {17     return a>b;18 }19 20 int main()21 {22     while(scanf("%d%d",&n,&k)!=EOF)23     {24         memset(dp,0,sizeof(dp));25         memset(a,0,sizeof(a));26         for(int i=1; i<=n; i++)27         {28             scanf("%d",&a[i]);29         }30         sort(a+1,a+n+1,cmp);31         for(int i=1; i<=k; i++)32         {33             dp[i][i*2]=dp[i-1][i*2-2]+sqr(a[i*2-1]-a[i*2]);34             for(int j=i*2+1; j<=n; j++)35             {36                 dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+sqr(a[j-1]-a[j]));37             }38         }39         printf("%d\n",dp[k][n]);40     }41     return 0;42 }