商场有n个物品，每个物品有一个价格a[i]，每个物品至多购买1次。商场有m个折扣活动，用(x[i],y[i])表示一次购买x[i]个物品可以免去最便宜的y[i]个物品的价格。问购买恰好k个物品的最小总价格。
https://codeforces.com/contest/1154/problem/F
前面的贪心很显然，排序贪心选最小的k个物品，每个x相同的折扣贪心选y最小的。后面的贪心并没想到，每次选择购买的物品都是连续的一段。最后设dp[i]表示购买了i个物品的最小值，然后枚举一次购买j个物品，用一个前缀和加速更新即可。
msv(dp, LINF);
cmin(dp[0], 0LL);
for(int i = 1; i <= k; ++i) {
for(int j = 1; j <= i; ++j)
cmin(dp[i], dp[i - j] + sum(i - y[j] + 1, i));
}
printf("%lld\n", dp[k]);
https://codeforces.com/contest/883/problem/I
将n个物品分为若干组，每组的大小至少为k，求每组的极差的最大值的最小值。
求最大值的最小值，容易想到二分极差D，但可惜check不能贪心为“刚刚超过D的时候多分一组”，因为这样可能会导致最后一组不足k个。这里要换一种思路，设状态为dp[i]表示是否存在一种方法，把[1,i]的物品完整分为若干组，且满足每组极差不超过D，且每组的数量至少为k。那么转移为dp[i]|=dp[j]，枚举j从0到i-k+1，且极差不超过D，这个是一个双指针确定的或和。
bool check(int D) {
dp[0] = 1;
int L = 0, R = 0, cnt = 1;
for(int i = 1; i <= n; ++i) {
while((i - (R + 1 + 1) + 1) >= k) {
++R;
cnt += dp[R];
}
while(a[i] - a[L + 1] > D) {
cnt -= dp[L];
++L;
}
dp[i] = (L <= R) && (i - (R + 1) + 1 >= k) && (cnt > 0);
}
return dp[n];
}