2020牛客寒假算法基础集训营2 H.施魔法
链接：
https://ac.nowcoder.com/acm/contest/3003/H
思路：
先排序，再dp，dp[i]表示用掉前i个元素的最小值，转移方程 dp[i] = min{dp[j]+a[i]-a[j]},j∈[i,j-k+1], 维护dp[j]-a[j]的前缀最小值即可
代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 3e5 + 7; 4 int dp[N], pre, a[N], n, k; 5 int main() { 6 scanf("%d%d", &n, &k); 7 for (int i = 1; i <= n; ++i) scanf("%d", a + i); 8 sort(a + 1, a + 1 + n); 9 pre = -a[1]; 10 for (int i = 1; i < k; ++i) dp[i] = 2e9; 11 for (int i = k; i <= n; ++i) { 12 dp[i] = pre + a[i]; 13 pre = min(pre, dp[i - k + 1] - a[i - k + 2]); 14 } 15 cout << dp[n]; 16 return 0; 17 }