题目
Shirotsume 来到了回转寿司店。从现在开始，Shirotsume 所在的柜台会依次放上N盘寿司。第 \(i\) 盘出现的寿司的美味度为 \(A_i\) 。
Shirotsume 决定拿起自己喜欢的寿司吃，但也考虑到其他客人的感受，决定不拿连续的 \(K\) 盘 及 \(K\) 盘以上的寿司。
请求出 Shirotsume 所吃的寿司的美味值的总和的最大值。
限制：
- \(2 \leqslant K \leqslant N \leqslant 2 \times 10^5\)
- \(1 \leqslant A_i \leqslant 10^9\)
算法分析
原题等价于求 Shirotsume 不吃的寿司的美味值总和的最小值 \(S\)。那么，答案就是所有寿司的美味值总和减去 \(S\) 。
记 dp[i] 表示在前 \(i\) 个寿司中，决定不吃第 \(i\) 个寿司时，不吃的寿司的美味值总和的最小值
由于不能吃连续的超过 \(K-1\) 盘的寿司，所以转移方程为
\[dp[i] = \min\limits_{j = i-K}^{i-1} dp[j] + A_i \]暴力的时间复杂度为 \(O(NK)\)，可以用线段树将转移复杂度降为 \(O(\log N)\)
代码实现
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
ll op(ll a, ll b) { return min(a, b); }
ll e() { return 1e18; }
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
ll ans = 0;
rep(i, n) ans += a[i];
segtree<ll, op, e> t(n);
rep(i, k) t.set(i, a[i]);
for (int i = k; i < n; ++i) {
ll now = t.prod(i-k, i)+a[i];
t.set(i, now);
}
ans -= t.prod(n-k, n);
cout << ans << '\n';
return 0;
}