施魔法

施魔法
https://ac.nowcoder.com/acm/contest/3003/H

先从小到大排序，极差转换为--连续一段数尾部和开头的差值
DP[i]就是前i个元素以i为尾划分段的最小值
i可以是 作为前一段的新尾，DP[i]=DP[i-1]-A[i-1]+A[i]
也可是新开一段k，作为段尾 DP[i]=DP[i-k]-A[i-k+1]+A[i] (A[i-k+1]是头，A[i]是尾)
则动态转移方程为 DP[i]=min(DP[i-1]-A[i-1]+A[i],DP[i-k]-A[i-k+1]+A[i])
需要注意的是1~k必须组成一个段，所以循环从 k+1 开始
注意：能够新开一段最早是从k+1为头开始，一开始对DP数组进行初始化操作使其为INF，使得其进行
操作时，在k+1之前不能取其为头
另需记得：DP[k]=A[k]-A[1]

#pragma warning (disable :4996)
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 10;

int n, k;
int M[N];
int DP[N];
int main() {
    scanf("%d %d", &n,&k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &M[i]);
    }
    sort(M+1, M + n+1);
    for (int i = 1; i <= n; i++)
        DP[i] = INF;
    DP[k] = M[k] - M[1];
    for (int i = k+1; i <= n; i++) {
        DP[i] = min(DP[i - 1] - M[i - 1] + M[i], DP[i - k ] - M[i - k + 1] + M[i]);
    }
    cout << DP[n] << endl;

}