[BZOJ 1855] 股票交易

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 ;

}

巴特西

[BZOJ 1855] 股票交易

Link:

Solution:

Code:

最新文章

热门文章