Link:
Solution:
比较明显的$dp$模型
令$dp[i][j]$为第$i$天持有$j$支股票时的最大利润
对其购买股票和售出股票分别$dp$,这里以购买为例:
$dp[i][j]=max\{ dp[lst][k]-ap*(j-k)\}$
发现可以将递归式转化为仅与$k$相关的$dp[lst][k]+ap*k$和仅与$j$相关的$ap*j$
于是可以利用单调队列将复杂度降到$O(n)$,时刻保持$j-k\le as$即可
要注意初始化,一开始要先全置为$-INF$
对于$[0,as]$的项的初始值为$max(dp[i-1][j],-ap*j)$
Code:
#include <bits/stdc++.h> using namespace std;
#define X first
#define Y second
typedef pair<int,int> P;
const int MAXN=,INF=<<;
P q[MAXN];
int l,r,n,mx,sep,res=-INF;
int ap,bp,as,bs,lst,dp[MAXN][MAXN]; int main()
{
scanf("%d%d%d",&n,&mx,&sep);
for(int i=;i<MAXN;i++) for(int j=;j<MAXN;j++)
dp[i][j]=-INF;
for(int i=;i<=n;i++)
{
scanf("%d%d%d%d",&ap,&bp,&as,&bs);
for(int j=;j<=as;j++) dp[i][j]=-ap*j;
for(int j=;j<=mx;j++) dp[i][j]=max(dp[i][j],dp[i-][j]); int lst=i-sep-;
if(lst<) continue;
l=;r=;
for(int j=;j<=mx;j++)
{
while(l<=r&&j-q[l].X>as) l++;
while(l<=r&&q[r].Y<=dp[lst][j]+ap*j) r--;
q[++r]=P(j,dp[lst][j]+ap*j);
dp[i][j]=max(dp[i][j],q[l].Y-ap*j);
} l=;r=;
for(int j=mx;j>=;j--)
{
while(l<=r&&q[l].X-j>bs) l++;
while(l<=r&&q[r].Y<=dp[lst][j]+bp*j) r--;
q[++r]=P(j,dp[lst][j]+bp*j);
dp[i][j]=max(dp[i][j],q[l].Y-bp*j);
}
res=max(res,dp[i][]);
}
printf("%d",res);
return ;
}