P1725 琪露诺 单调队列优化DP
P1725 琪露诺
/*
P1725 琪露诺
单调队列优化DP
状态很好定义和转移：dp[i]表示以i结束的合法状态经过的最大数字和，通过dp[j](i-R<=j<=i-L)的最大值从前向后转移。
但是复杂度太大，高达O(n(R-L))，可以看作O(n^2)，显然不行，
考虑到每次转移都是从一段定长区间[i-R,i-L]找dp[j]的最值，没必要每次都枚举一遍，很容易想到用线段树维护dp数组达到查询O(log n)，但时间仍然不理想且码量很大。
由于区间定长，与滑动窗口求区间最值很类似，所以可以用单调队列维护当前可以来转移的dp[j]的区间，找到最大值，
每次i增加就让右端的dp[i-L]就新从右端的对位入队(因为i-L是能转移到i的最右边的编号)，并且弹出队尾直到队列单调递减(新加的数不小于队尾的数就弹出)，
由于还需要删除队列内不在当前区间内的过期数据，需要用到队列元素的编号，所以队列直接存f的下标即可。
Tips：单调队列滑动窗口时，队头在右，队尾在左，队头比队尾更老，所以出队要从队头，而从队尾新加元素，为了查询最大值，让队列单调递减，队头即为最大值。
为什么要这么维护？便于先进队的元素先出队，消除对最值的影响，又由于窗口是从左到右滑动的，所以队尾入队更方便理解，队列中元素的相对位置和原序列中是一样的。
出错：最开始dp赋初值放在输入n后面了（我是**）
原来被Hack的数据：
input：
6 2 2
0 1 -1 1 -1 1 -1
output：
-3
如果没赋初值极小：2
这是因为实际上3号点和5号点都是无法到达的，需要使其dp初值极小以保证不会更新ans，错误答案就是因为进行了这样错误的转移。
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f;
int dp[N],n,L,R,a[N],q[N],tail,head,ans=-inf;
int main()
{
scanf("%d%d%d",&n,&L,&R);
for(int i=1;i<=n;i++) dp[i]=-inf;//一定要赋初值为极小，因为数字可以是负的
dp[0]=0;//题中给出第0个格子数字保证为0
for(int i=0;i<=n;i++) scanf("%d",&a[i]);
for(int i=L;i<=n;i++)
{
while(head<tail&&dp[i-L]>=dp[q[tail-1]]) tail--;//队尾出队直到队列单减
q[tail++]=i-L;//右边新加的数入队
while(head<tail&&q[head]<i-R) head++;//在区间外的数出队
dp[i]=dp[q[head]]+a[i];//此时的队头一定是最大值，直接更新
if(i+R>n) ans=max(ans,dp[i]);//更新答案
}
printf("%d",ans);
return 0;
}