【Luogu】P2569股票交易（单调队列优化DP）

　　题目链接

　　首先这题可以肯定的是朴素DP秒出。然后单调队列优化因为没接触过所以不会emmm

　　而且脑补没补出来

　　坐等四月省选倒数第一emmm

　　心态爆炸，偷懒放题解链接

#include<cstdio>

#include<cstring>

#include<cctype>

#include<cstdlib>

#include<algorithm>

#define maxn 2020

#define INF 0x7fffffff

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

int f[maxn][maxn];

struct Day{

    int vali,valo,numi,numo;

}q[maxn];

struct File{

    int que[maxn*],h,t;

    File(){h=;t=;}

    void clear(){h=;t=;}

}s;

int ans;

int main(){

    memset(f,-/,sizeof(f));

    int n=read(),m=read(),w=read();

    for(int i=;i<=n;++i)

        q[i]=(Day){read(),read(),read(),read()};

    for(int i=;i<=n;++i)    f[i][]=;

    for(int i=;i<=n;++i){

        for(int j=;j<=q[i].numi;++j)    f[i][j]=max(f[i-][j],-j*q[i].vali);

        for(int j=m;j>=;--j)            f[i][j]=max(f[i][j],f[i-][j]);

        if(i-w-<)    continue;

        int last=i-w-;

        s.clear();

        for(int j=;j<=m;++j){

            while(s.h<=s.t&&s.que[s.h]<j-q[i].numi)    s.h++;

            while(s.h<=s.t&&f[last][s.que[s.t]]+s.que[s.t]*q[i].vali<=f[last][j]+j*q[i].vali)    s.t--;

            s.que[++s.t]=j;

            f[i][j]=max(f[i][j],f[last][s.que[s.h]]-q[i].vali*(j-s.que[s.h]));

        }

        s.clear();

        for(int j=m;j>=;--j){

            while(s.h<=s.t&&s.que[s.h]>j+q[i].numo)    s.h++;

            while(s.h<=s.t&&f[last][j]+q[i].valo*j>=f[last][s.que[s.t]]+s.que[s.t]*q[i].valo)    s.t--;

            s.que[++s.t]=j;

            f[i][j]=max(f[i][j],f[last][s.que[s.h]]+q[i].valo*(s.que[s.h]-j));

        }

    }

    for(int i=;i<=m;++i)    ans=max(ans,f[n][i]);

    printf("%d",ans);

    return ;

}