单调队列
本题要点：
1、转态表示：
f[i]表示在i点能获得的最大冰点值
2、状态转移方程：
f[i] = ice[i] + max{f[j]}(i - r <= j <= i - l)
3、 对于当前的i， f[i的状态由区间 [i - r, i - l] 的状态转移过来。
用一个单调队列 ，记录区间 [i - r, i - l] 的状态的最大值。（记录下标即可）。
队列的值是单调递减的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MaxN = 200010, INF = 0x3f3f3f3f;
int ice[MaxN];
int f[MaxN]; //f[i]表示在i点能获得的最大冰点值
int n, l, r;void solve()
{
queue<int> q;for(int i = 0; i < l; ++i){
f[i] = -INF;}f[0] = ice[0];for(int i = l; i <= n; ++i){
if(!q.empty()) //下标范围超出 r 的点，弹出。{
int tp = q.front();if(i - tp > r){
q.pop();}}int index = i - l; //加入队列的下标while(!q.empty()){
int j = q.front();if(f[j] < f[index]){
q.pop(); }else{
q.push(index);break;}}if(q.empty()){
q.push(index);}int front = q.front();f[i] = f[front] + ice[i];}int ans = -INF;for(int i = 1; i <= n; ++i){
if(i + r > n){
ans = max(f[i], ans);}}printf("%d\n", ans);
}int main()
{
scanf("%d%d%d", &n, &l, &r);for(int i = 0; i <= n; ++i){
scanf("%d", &ice[i]);}solve();return 0;
}/* 5 2 3 0 12 3 11 7 -2 *//* 11 */