学步园

/*可以用单调队列优化的DP一般是用于限定长度的区间，且区间有整体移动的趋势。即每一个元素是逐次进出区间，且只有一次。这样的题目一般都是有比较明显的模板。下面的这个就是集训的时候学长给的模板。感觉挺好写和理解。不过综合对比时间效率。感觉不一定是最高效的。
题意是给你固定的区间长度范围。求该序列首端和末端的和最大值。
简单。维护一个单调队列进行优化即可。有些细节看代码的注释。*/
#include <iostream>
#include <stdio.h>
#include <cstring>
#define maxn 100010
//#define inf -1000000000
#define inf 0x7fffffff
using namespace std;
struct node
{
    int num,id;
    node() {}
    node(int _num,int _id)
    {
        num=_num;
        id=_id;
    }
} q[maxn];
int dp[maxn];
int a[maxn];
int main()
{
    int n,m,len;
    while(scanf("%d",&len)==1)
    {
        dp[0]=0;
        scanf("%d%d",&n,&m);
        for(int i=1; i<=len; i++)
            if(i<=n-1) dp[i]=inf;//1到n-1没有意义        
        int head=0,rear=0;
        q[rear++]=node(0,1);
        for(int i=1; i<=len; i++)
        {
            scanf("%d",&a[i]);
            if(i>=n)
            {
                while(head<rear&&q[rear-1].num<=dp[i-n]+a[i-n+1]) rear--;//将i-n加入,i-m已经在队列中.
                q[rear++]=node(dp[i-n]+a[i-n+1],i-n);
                while(head<rear&&i-q[head].id>m) head++;//注意是>m..知道找到<=m时跳出.<=m是我们需要的情况
                dp[i]=q[head].num+a[i];
            }
        }
        printf("%d\n",dp[len]);
    }
    return 0;
}