传送门
解题思路
设dp[i][j]为前i天第i天结束时有j张股票的最大收益，
首先令dp[i][j]=dp[i-1][j]。
买入转移方程：
[dp[i][j]=max(dp[i][j],dp[i-w-1][k]-(j-k)*ap)quadquad k=[j-as,j]
]
卖出转移方程：
[dp[i][j]=max(dp[i][j].dp[i-w-1][k]+(k-j)*bp)quadquad k=[j,j+bs]
]
把括号去掉就可以用单调队列优化。
AC代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<deque>
using namespace std;
int n,maxp,w,ans,last,ap,bp,as,bs,dp[2005][2005];
int main(){
ios::sync_with_stdio(false);
cin>>n>>maxp>>w;
memset(dp,-0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++){
cin>>ap>>bp>>as>>bs;
deque<int> q;
last=max(0,i-w-1);
for(int j=0;j<=maxp;j++){
dp[i][j]=dp[i-1][j];
}
for(int j=0;j<=maxp;j++){
while(!q.empty()&&j-q.front()>as) q.pop_front();
while(!q.empty()&&dp[last][q.back()]+q.back()*ap<dp[last][j]+j*ap) q.pop_back();
q.push_back(j);
if(!q.empty()) dp[i][j]=max(dp[i][j],dp[last][q.front()]-(j-q.front())*ap);
}
while(!q.empty()) q.pop_back();
for(int j=maxp;j>=0;j--){
while(!q.empty()&&q.front()-j>bs) q.pop_front();
while(!q.empty()&&dp[last][q.back()]+q.back()*bp<dp[last][j]+j*bp) q.pop_back();
q.push_back(j);
if(!q.empty()) dp[i][j]=max(dp[i][j],dp[last][q.front()]+(q.front()-j)*bp);
}
}
for(int i=0;i<=maxp;i++) ans=max(ans,dp[n][i]);
cout<<ans;
return 0;
}