喵哈哈村的魔法考试 Round #19 (Div.2) D & tyvj1305 单调队列优化的dp

题目链接：

http://qscoj.cn/problem/130/

题意：

给你n个数a[1]，a[2]，a[3]，......，a[n]，然后再给你一个k。

定义sum[l,r]=a[l]+a[l+1]+a[l+2].....+a[r-1]+a[r]，但是必须满足r-l+1<=k

思路：

http://blog.csdn.net/oiljt12138/article/details/51174560

f(i) = sum[i]-min{sum[k]|i-M≤k≤i} 

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//////////////////////////////////////////////////////////////////////////
const int maxn = 1e6+10;

int s[maxn];

struct node{
    int v,id;
}q[maxn];

int main(){
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        int x = read();
        s[i] = x+s[i-1];
    }

    int head=0,tail=0;
    q[0].v=0,q[0].id=0;
    ll ans = -INF;
    for(int i=1; i<=n; i++){
        ll re = s[i];
        re -= q[tail].v;
        ans = max(ans,re);
        while(tail<=head && q[head].v>s[i]) head--;
        q[++head].v = s[i];
        q[head].id = i;
        while(tail<=head && q[tail].id<=i-m) tail++;
    }

    cout << ans << endl;
    

    return 0;
}

// http://www.tyvj.cn/p/1305