1 条题解
-
0
题目转化一下，先选所有数字，然后删除其中一部分不选，那么相邻两个删除的数字距离不能超过k。
用f[i]表示删除第i个数字，且相邻两个删除的数字距离不能超过k时，删去数字的最小的和。可以用单调队列维护区间f[i]的最小值来优化。
核心代码
tail = 1; head = 1; q[1] = 0; f[0] = 0; for(int i=1; i<=n; ++i) { while(head<=tail && q[head] < i-k) head++; f[i] = f[q[head]] + a[i]; while(head<=tail && f[q[tail]] >= f[i]) tail--; q[++tail] = i; }
- 1