1 /*
 2 Author:    Leo.W
 3 Descriptipn:    一系列的n件物件，只能搬2*k件，且疲勞度為每次搬得兩件物品的質量差的平方，求最小疲勞度    
 4 How to Do:    DP動態(tài)規(guī)劃，狀態(tài)轉移類似背包問題，先把所有物品排序，再將相鄰物品平方差求出。
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10 #define min(a,b) (a)<(b)?(a):(b)
11 int d[2001];
12 int dp[2002][1001];
13 int main(){
14     //freopen("in.txt","r",stdin);
15     int n,k;
16     while (scanf("%d%d",&n,&k)!=EOF){
17         int i,j;
18         for(i=1;i<=n;i++)    scanf("%d",&d[i]);
19         sort(d+1,d+n+1);
20         for(i=1;i<=n-1;i++)    d[i]=(d[i]-d[i+1])*(d[i]-d[i+1]);
21         memset(dp,127,sizeof(dp));
22         for(i=0;i<=n;i++)
23             dp[i][0]=0;
24         for(i=2;i<=n;i++){
25             for(j=1;j*2<=i;j++){//關鍵代碼 注意不要重復 所以只能采用二維
26                 dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+d[i-1]);
27             }
28         }
29         printf("%d\n",dp[n][k]);
30     }
31     return 0;
32 }
33