题意
略
数据范围:$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;
}