[BZOJ 1855] 股票交易

时间:2024-07-08 11:36:44

Link:

BZOJ 1855 传送门

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 ;
}