[SCOI2010] 股票交易

题意

对于一个股市,给出第 天买 / 卖股票的价格和买 / 卖股票的数量,依次为 .

并要求手上的股票数不超过 ,两次交易的间隔时间至少 天(买卖都各算一次交易),初始时有无数多的钱和 0 股票,求 天后的最大净利润。

.

分析

观察数据范围就知道设 表示第 i 天,交易后股票数为 j 时的净利润

有 4 种情况的转移

从 0 开始买

不交易

买股票

买入

因为有不交易的转移,所以不用考虑第一维在 的情况

卖股票

卖出

单调队列

直接转移,复杂度是 .

我们化一下转移 3 的方程

那就是单调队列没错了

同理,化一下转移 4 的方程

于是复杂度 .

注意初始化成 .

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int T=2003,MaxP=2003;
int t,maxp,w;
int ap[T],bp[T],as[T],bs[T];
int f[T][MaxP];

int main(){scanf("%d%d%d",&t,&maxp,&w);
    for(int i=1;i<=t;i++)scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
//target: max{f[t][0..maxp]}.
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=t;i++){int q1[MaxP][2],l1=1,r1=0;
        int q2[MaxP][2],l2=1,r2=0;
        if(i-w-1>=0){// 初始化队列
            //p=[0,-1]=none.#3
            //p=[1,min(maxp,bs[i])].#4
            for(int p=1;p<=min(maxp,bs[i]);p++){int cur=f[i-w-1][p]+p*bp[i];
                while(l2<=r2&&q2[r2][0]<=cur)--r2;
                q2[++r2][0]=cur,q2[r2][1]=p;
            }
        }
        for(int j=0;j<=maxp;j++){if(j<=as[i])f[i][j]=max(f[i][j],-ap[i]*j);//#1
            f[i][j]=max(f[i][j],f[i-1][j]);//#2
            if(i-w-1<0)continue;
            if(l1<=r1)f[i][j]=max(f[i][j],q1[l1][0]-j*ap[i]);//#3
            if(l2<=r2)f[i][j]=max(f[i][j],q2[l2][0]-j*bp[i]);//#4
            // 下面维护单调队列
            //add(j),del(j-as[i]).#3
            int p=j,cur=f[i-w-1][p]+p*ap[i];
            while(l1<=r1&&q1[r1][0]<=cur)--r1;
            q1[++r1][0]=cur,q1[r1][1]=p;
            while(l1<=r1&&q1[l1][1]<=j-as[i])++l1;
            //add(j+1+bs[i]),del(j+1).#4
            if(j+1+bs[i]<=maxp){int p=j+1+bs[i],cur=f[i-w-1][p]+p*bp[i];
                while(l2<=r2&&q2[r2][0]<=cur)--r2;
                q2[++r2][0]=cur,q2[r2][1]=p;
            }
            while(l2<=r2&&q2[l2][1]<=j+1)++l2;
        }
    }
    int ans=-1e9;
    for(int i=0;i<=maxp;i++)ans=max(ans,f[t][i]);
    printf("%d",ans);
    return 0;
}

  转载请注明: Sshwy's Blog [SCOI2010] 股票交易

 上一篇
SCOI2008 奖励关 SCOI2008 奖励关
题意在奖励关里,系统将依次随机抛出 k 次宝物,每次你都可以选择吃或者不吃。宝物一共有 n 种,第 k 次抛出各个宝物的概率均为 。 获取第 i 种宝物将得到 分( 可以是负数),但第 i 种
2019.01.17
下一篇 
[HAOI2010] 软件安装 [HAOI2010] 软件安装
题意有 个软件和空间为 的硬盘,每个软件有一个占用空间 和价值 和一个依赖软件 表示没有依赖)。一个软件要安装,仅当其依赖软件已安装且硬盘空间足够,求最大价值. $N\le
2019.01.16
  目录