洛谷P2569 [SCOI2010]股票交易（单调队列）

传送门

惭愧……这种题目都没看出来……

首先，我们用$dp[i][j]$表示在第$i$天，手上有$j$股时的最大收益

第一，我们可以直接买股票，即$dp[i][j]=-j*AP_i$，这个直接计算即可

第二，我们可以不操作，那么$dp[i][j]=max(dp[i][j],dp[i-1][j])$

第三种，我们买股票，那么$dp[i][j]=max(dp[i][j],dp[i-w-1][k]+k*AP_i-j*AP_i)$

第四种，我们卖股票，那么$dp[i][j]=max(dp[i][j],dp[i-w-1][k]+k*BP_i-j*BP_i)$

然后发现三四两种情况把与$j$有关的提出来之后，里面的可以用单调队列优化

顺便注意情况三要从小到大搞，情况四要从大到小搞

//minamoto
#include<bits/stdc++.h>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
inline int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
const int N=2005;
int n,m,w,ans,h,t,q[N],dp[N][N];
int main(){
//    freopen("testdata.in","r",stdin);
    n=read(),m=read(),w=read();
    memset(dp,0xef,sizeof(dp));
    for(int i=1;i<=n;++i){
        int ap=read(),bp=read(),as=read(),bs=read();
        for(int j=0;j<=as;++j) dp[i][j]=-j*ap;
        for(int j=0;j<=m;++j) cmax(dp[i][j],dp[i-1][j]);
        if(i<=w) continue;
        h=1,t=0;
        for(int j=0;j<=m;++j){
            while(h<=t&&q[h]<j-as) ++h;
            while(h<=t&&dp[i-w-1][q[t]]+q[t]*ap<=dp[i-w-1][j]+j*ap) --t;
            q[++t]=j,cmax(dp[i][j],dp[i-w-1][q[h]]+q[h]*ap-j*ap);
        }
        h=1,t=0;
        for(int j=m;j>=0;--j){
            while(h<=t&&q[h]>j+bs) ++h;
            while(h<=t&&dp[i-w-1][q[t]]+q[t]*bp<=dp[i-w-1][j]+j*bp) --t;
            q[++t]=j,cmax(dp[i][j],dp[i-w-1][q[h]]+q[h]*bp-j*bp);
        }
    }
    for(int i=0;i<=m;++i) cmax(ans,dp[n][i]);
    printf("%d
",ans);
    return 0;
}