D. Minimization
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You've got array A, consisting of n integers and a positive integer k. ArrayA is indexed by integers from 1 to n.

You need to permute the array elements so that value

<center class="tex&#45;equation"> </center> became minimal possible. In particular, it is allowed not to change order of elements at all.
Input

The first line contains two integers n, k (2 ≤ n ≤ 3·105,1 ≤ k ≤ min(5000, n - 1)).

The second line contains n integers A[1], A[2], ..., A[n] ( - 109 ≤ A[i] ≤ 109), separate by spaces — elements of the arrayA.

Output

Print the minimum possible value of the sum described in the statement.

Examples
Input 
3 2
1 2 4
Output 
1
Input 
5 2
3 -5 3 -5 3
Output 
0
Input 
6 3
4 3 4 3 2 5
Output 
3
Note

In the first test one of the optimal permutations is 1 4 2.

In the second test the initial order is optimal.

In the third test one of the optimal permutations is 2 3 4 4 3 5.

【参考blog】http://blog.csdn.net/u014800748/article/details/47905237

【题意】给定一个长度为n的序列，给定一个1<=k<=min(5000,n-1)，通过重新排列，求最小的

<center class="tex&#45;equation"> </center> 【解题方法】 根据题意，我们需要在数组中，每相邻k个数要进行一次求和运算，那么，我们不妨把从下标i开始计算的数全部找出来，把他们看做一组，即下标为i,i+k,i+2k,...i+(n-1-i)/k*k这些数看做一个组的，我们发现，最多只能有k组(i只能从0取到k-1，再往后就会出现重复计算)。而且，只有n%k个组是包含n/k+1个数，k-n%k个组是包含n/k个数，我们把具有n/k+1个数的组叫“大组”，有n/k个数的组叫“小组”,这样，问题就转化为如何挑选一些大组（剩下的都是小组），使得最终的ans最小。

       首先考虑如何才能让一个组的结果对答案的贡献尽量小。由于组内的数都是原数组中每隔k个数取的，因此，对答案的贡献就是sum{Ai-Ai+1|i from 0 to m-1,m是该组的元素个数}。可以发现，只有当组内元素都从小到大排列之后，该组的贡献值最小，等于abs(Am-1-A0)，这就告诉我们，首先要对原数组进行排序。我们定义状态dp(i,j)表示一共有i个组，其中j个为大组时的答案，那么不难得到如下的状态转移方程：

dp(i+1,j+1)=min(dp(i+1,j+1),dp(i,j)+a[idx+small]-a[idx]);

dp(i+1,j)=min(dp(i+1,j),d(i,j)+a[idx+small-1]-a[idx]);

其中，small=n/k, idx=i*s+j（因为j*(small+1)+(i-j)*small=i*small+j，表示下一个组的起始下标），那么如果作为大组处理，最后一个元素就是a[idx+small]，作为小组处理，就是a[idx+small-1]。这样，最终的答案就是d(k,large)(large=n%k)。


[AC 代码]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL inf = 1e15;
LL dp[5010][5010];
int a[300010];
int n,k;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0; i<n; i++) scanf("%lld",&a[i]);
    sort(a,a+n);
    int small=n/k;//小组的个数
    int large=n%k;//大组的最大组数
    for(int i=0; i<k+1; i++)
        for(int j=0; j<k+1; j++) dp[i][j]=inf;
    dp[0][0]=0;
    for(int i=0; i<k; i++){
        for(int j=0; j<k; j++){
            if(dp[i][j]==inf) continue;
            int idx=i*small+j;//下一个组的起始下标
            if(idx+small<n) dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+a[idx+small]-a[idx]);//下一个组为大组
            if(idx+small-1<n) dp[i+1][j]=min(dp[i+1][j],dp[i][j]+a[idx+small-1]-a[idx]);//下一个组为小组
        }
    }
    printf("%lld\n",dp[k][large]);
    return 0;
}