原题链接
我会暴力dp！
设 \(dp_i\) 为刚好到第 \(i\) 个格子的最大值。那么 \(dp_i\) 就可以从 \([i - RR, i - LL]\) 这段区间内转移。
则可以得出状态转移方程 \(dp_i = dp_{j} + a_i\) （\(j\) 在 \([i - RR, i - LL]\) 区间内）
暴力查询最大的 \(dp_j\)，时间复杂度\(O(n ^ 2)\)，可得 \(60\) 分。
我会单调队列！
发现每段区间像一个滑动窗口，于是用单调队列维护最大值。
时间复杂度 \(O(nlogn)\)，可以通过本题。
我会线段树！
发现转移类似于区间查询，更新类似于单点修改，于是用线段树维护区间最大值。
每次查询查询 \([i - RR, i - LL]\) 区间内的最大值用来状态转移，更新完 \(dp_i\) 后单点修改 \(tree_i\) 的值，方便下一次转移。
时间复杂度 \(O(nlogn)\)，可以通过本题。
code（线段树）：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int w[800005], n, dp[200005], a[200005];
int LL, RR, maxx = -1e18;
bool InRange(int l, int r, int L, int R)
{return (l >= L) && (r <= R);
}
bool OutofRange(int l, int r, int L, int R)
{return (l > R) || (r < L);
}
void pushup(int u)
{w[u] = max(w[u * 2], w[u * 2 + 1]);
}
void update(int u, int l, int r, int L, int R, int x)
{if(InRange(l, r, L, R)){w[u] = x;return ;}if(OutofRange(l, r, L, R)) return ;int mid = l + r >> 1;update(u * 2, l, mid, L, R, x);update(u * 2 + 1, mid + 1, r, L, R, x);pushup(u);
}
int query(int u, int l, int r, int L, int R)
{if(InRange(l, r, L, R)){return w[u];}if(OutofRange(l, r, L, R)){return -1e18;}int mid = l + r >> 1;return max(query(u * 2, l, mid, L, R), query(u * 2 + 1, mid + 1, r, L, R));
}
void build(int u, int l, int r)
{if(l == r){if(l != 0) w[u] = -1e18;else w[u] = 0;return ;}int mid = l + r >> 1;build(u * 2, l, mid);build(u * 2 + 1, mid + 1, r);pushup(u);
}
signed main()
{cin >> n >> LL >> RR;for(int i = 0;i <= n;i ++){cin >> a[i];}build(1, 0, n);dp[0] = a[0];update(1, 0, n, LL, LL, dp[0]);for(int i = LL;i <= n;i ++){dp[i] = query(1, 0, n, i - RR, i - LL) + a[i];// cout << "qweqw0" << i - LL << " " << i - RR << endl;
// cout << query(1, 0, n, i - RR, i - LL) << endl;update(1, 0, n, i, i, dp[i]);}for(int i = n - RR + 1;i <= n;i ++){maxx = max(maxx, dp[i]);}cout << maxx;
}