施魔法题解报告

dp

第一眼看到这道题还以为是标准的划分dp $O(n^2)$ ，弄了好久时间复杂度还是超
现在总算懂了，这题是 $O(n)$ 的dp
首先我们需要排序，把这些元素从小到大排好，这样确保可以直接划分(自己想一下)，并且这一段的最大值是这一段的尾，最小值是这一段的头，相当于连区间最大值最小值的线段树都不用打了
用 $f[i]$ 表示前 $i$ 个元素以 $i$ 为尾划分段后的最小值
那么 $i$ 可以是把前一个段的尾巴拆下，装到自己这里，也就是把上一段的尾延伸到第 $i$ 个元素范围是 $last-head$ ~ $i$
同时也可以作为新一段的尾，范围是 $i-k+1$ ~ $i$
那动态转移方程式就是 $f[i]=min(f[i-1]-a[i-1]+a[i],f[i-k]-a[i-k+1]+a[i]);$
我们要确保最开始的 $k$ 个必须组成一个段，最优值后面还可以拆，但是前 $k$ 元素不能再拆，所以 $for$ 是从 $k+1$ 开始的
贴上蒟蒻代码:

#include<bits/stdc++.h>
#define maxn 300010
#define INF 999999999
using namespace std;

int n,k;
int a[maxn],f[maxn];

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i) f[i]=INF;
    f[k]=a[k]-a[1];
    for(int i=k+1;i<=n;++i)
        f[i]=min(f[i-1]-a[i-1]+a[i],f[i-k]-a[i-k+1]+a[i]);
    printf("%d",f[n]);
    return 0;
}