首先易得对于每个礼盒所买的$i、j$，当且仅当$w_i、w_j$相邻时为最优策略，故我们先按照$w_i$排序，然后用DP求解。

设$f_\text{i,j}$为枚举到i件商品，j个礼盒的最小不和谐值，我们可以得到以下状态转移方程：

1.不选择$i、i-1$：$f_\text{i,j}=f_\text{i-1,j}$

2.选择$i、i-1$($i\geq3*j$，得确保所有礼盒都有3件商品)：$f_\text{i,j}=f_\text{i-2,j-1}+w_i-w_\text{i-1}$

接下来是初始化，令$f_\text{i,0}=0,f_\text{i,j}$$(0\leq i\leq n,1\leq j\leq k)$最终答案即为$f_\text{n,k}$ 时间复杂度为$O(n^2)$

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int a[N];
int f[N][N];
int n,k;
int main(){
	memset(f,0x3f,sizeof f);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	f[0][0]=0;
	for(int i=1;i<=n;i++)f[i][0]=0;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=k;j++){
			f[i][j]=f[i-1][j];
			if(i>=j*3)f[i][j]=min(f[i][j],f[i-2][j-1]+a[i]-a[i-1]);
		}
	}
	printf("%d\n",f[n][k]);
	return 0;
}