题意

略

数据范围：$0 \le w,t \le 2000,1 \le p \le 2000,1 \le bp_i \le ap_i \le 1000,1 \le as_i,bs_i \le p$

题解

算法：动态规划
用$f[i][j]$表示第$i$天持有$j$股股票，前$i$天的最大收益
首先，若从第$i$天开始买股票，有$$f[i][j]=-ap_i \cdot j$$其中$j \in [0,as_i]$
其次，在不进行买卖的前提下，$f[i][j]$可以从前$1$天转移过来，即$$f[i][j]=\max(f[i][j],f[i-1][j])$$
现在考虑进行买卖的情况
若在第$i$天买入股票，应从允许交易的第$i-w-1$天转移过来，即$$f[i][j]=\max(f[i][j],f[i-w-1][k]-ap_i \cdot (j-k))$$其中$k$为第$i-w-1$天持有的股票数，$k \in [j-as_i,j)$
在第$i$天卖出股票同理$$f[i][j]=\max(f[i][j],f[i-w-1][k]+bp_i \cdot (k-j))$$其中$k \in (j,j+bs_i]$
需要注意的是，买入和卖出的转移方向相反，原因类似于背包
但是这样$dp$的复杂度为$O(n^3)$，需要进行优化
以买入为例，对于求$$\max(f[i-w-1][k]-ap_i \cdot (j-k))$$将含$j$项提出可得$$\max(f[i-w-1][k]+ap_i \cdot k)-ap_i \cdot j$$那么$\max$内只与$k$有关，考虑单调队列优化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2000+10;
const int SUP=0xc0c0c0c0;
int t,p,w;
int ap,bp,as,bs;
int hd,tl,ans=SUP;
int dp[N][N],mq[N];
int main(){
    memset(dp,0xc0,sizeof(dp));
    scanf("%d%d%d",&t,&p,&w);
    for(int i=1;i<=t;i++){
        scanf("%d%d%d%d",&ap,&bp,&as,&bs);
        for(int j=0;j<=as;j++)
            dp[i][j]=-ap*j;
        for(int j=0;j<=p;j++)
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
        if(i-w-1<=0)
            continue;
        hd=1,tl=0;
        for(int j=0;j<=p;j++){
            for(;hd<=tl && mq[hd]<j-as;hd++);
            for(;hd<=tl && dp[i-w-1][mq[tl]]+ap*mq[tl]<=dp[i-w-1][j]+ap*j;tl--);
            mq[++tl]=j;
            if(hd<=tl)
                dp[i][j]=max(dp[i][j],dp[i-w-1][mq[hd]]+ap*mq[hd]-ap*j);
        }
        hd=1,tl=0;
        for(int j=p;j>=0;j--){
            for(;hd<=tl && mq[hd]>j+bs;hd++);
            for(;hd<=tl && dp[i-w-1][mq[tl]]+bp*mq[tl]<=dp[i-w-1][j]+bp*j;tl--);
            mq[++tl]=j;
            if(hd<=tl)
                dp[i][j]=max(dp[i][j],dp[i-w-1][mq[hd]]+bp*mq[hd]-bp*j);
        }
    }
    for(int i=0;i<=p;i++)
        ans=max(ans,dp[t][i]);
    printf("%d",ans);
    return 0;
}