施魔法题解报告

dp

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

#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;
}