【bzoj1855】股票交易

  • 本文为博主原创，未经许可不得转载

设f[i][j]表示第i天拥有j股股票的最大收益

首先列出朴素的状态转移方程：

$f[i][j]=f[i-1][j]$

$f[i][j]=max{f[i-w-1][k]-(j-k)\times A[i]}　　(k>=j-AS[i])$

$f[i][j]=max{f[i-w-1][k]+(k-j)\times B[i]}　　(k<=max(MaxP,AS[i]+j))$

然后我们发现可以用单调队列维护$f[i-w-1][k]+k\times A[i]$和$f[i-w-1][k]+k\times B[i]$

这样就能把复杂度降到O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 2010
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
int n,maxp,w,ans,a[MAXN],b[MAXN],as[MAXN],bs[MAXN],q[MAXN],f[MAXN][MAXN];
inline int read(){
    int x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    n=read();  maxp=read();  w=read();  memset(f,-10,sizeof(f));
    for(int i=1;i<=n;++i)  a[i]=read(),b[i]=read(),as[i]=read(),bs[i]=read();
    for(int i=1;i<=n;++i){
        for(int j=0;j<=as[i];j++)  f[i][j]=-a[i]*j;
        for(int j=0;j<=maxp;++j)  cmax(f[i][j],f[i-1][j]);
        if(i-w-1<0)  continue;
        int head=0,tail=0;
        for(int j=0;j<=maxp;++j){
            while(head<tail&&q[head]<j-as[i])  ++head;
            while(head<tail&&f[i-w-1][j]+j*a[i]>=f[i-w-1][q[tail-1]]+q[tail-1]*a[i])  --tail;
            q[tail++]=j;
            if(head<tail) cmax(f[i][j],f[i-w-1][q[head]]-a[i]*(j-q[head]));
        }
        head=0,tail=0;
        for(int j=maxp;j>=0;--j){
            while(head<tail&&q[head]>j+bs[i])  ++head;
            while(head<tail&&f[i-w-1][j]+j*b[i]>=f[i-w-1][q[tail-1]]+q[tail-1]*b[i])  --tail;
            q[tail++]=j;
            if(head<tail) cmax(f[i][j],f[i-w-1][q[head]]+b[i]*(q[head]-j));
        }
    }
    for(int i=0;i<=maxp;++i)  cmax(ans,f[n][i]);
    printf("%d\n",ans);
    return 0;
}

本文标题:【bzoj1855】股票交易

文章作者:chty

发布时间:2017年04月09日 - 19时33分

最后更新:2018年03月02日 - 17时27分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,