首页 > 代码库 > 1855: [Scoi2010]股票交易[单调队列优化DP]

1855: [Scoi2010]股票交易[单调队列优化DP]

1855: [Scoi2010]股票交易

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1083  Solved: 519
[Submit][Status][Discuss]

Description

最近lxhgww又迷上了投资股票,通过一段时间的观察和学习,他总结出了股票行情的一些规律。 通过一段时间的观察,lxhgww预测到了未来T天内某只股票的走势,第i天的股票买入价为每股APi,第i天的股票卖出价为每股BPi(数据保证对于每个i,都有APi>=BPi),但是每天不能无限制地交易,于是股票交易所规定第i天的一次买入至多只能购买ASi股,一次卖出至多只能卖出BSi股。 另外,股票交易所还制定了两个规定。为了避免大家疯狂交易,股票交易所规定在两次交易(某一天的买入或者卖出均算是一次交易)之间,至少要间隔W天,也就是说如果在第i天发生了交易,那么从第i+1天到第i+W天,均不能发生交易。同时,为了避免垄断,股票交易所还规定在任何时间,一个人的手里的股票数不能超过MaxP。 在第1天之前,lxhgww手里有一大笔钱(可以认为钱的数目无限),但是没有任何股票,当然,T天以后,lxhgww想要赚到最多的钱,聪明的程序员们,你们能帮助他吗?

Input

输入数据第一行包括3个整数,分别是T,MaxP,W。 接下来T行,第i行代表第i-1天的股票走势,每行4个整数,分别表示APi,BPi,ASi,BSi。

Output

输出数据为一行,包括1个数字,表示lxhgww能赚到的最多的钱数。

Sample Input

5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1

Sample Output

3

HINT

对于30%的数据,0 < =W 对于50%的数据,0 < =W 对于100%的数据,0 < =W 
对于所有的数据,1 < =BPi < =APi < =1000,1 < =ASi,BSi < =MaxP

Source

Day1

[Submit][Status][Discuss]
/*方法:单调队列优化DP设f[i][j]代表前i天有j份股票时的最大利润。三种更新:1.不交易:f[i][j]=max(f[i][j],f[i-1][j]);2.买入:f[i][j]=max(f[i][j],f[i-w-1][k]-(j-k)*AP[i])(k>=j-AS[i]);3.卖出:f[i][j]=max(f[i][j],f[i-w-1][k]+(k-j)*BP[i])(k<=max(maxp,j+BS[i]))然后我们观察式子,第一种更新O(1)完成,第二和第三的时候如果枚举k的话复杂度承受不了,所以考虑怎么优化,显而易见第二三种是线性的,所以考虑到队列可不可行?于是整理表达式,发现可行,则按照f[i-w-1][k]+k*AP[i]以及f[i-w-1][k]+k*BP[i]维护递减即可。*/#include<cstdio>#include<cstring>#include<iostream>#define set(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}    return x*f;}const int N=2001;int n,maxp,w,ans,AP[N],BP[N],AS[N],BS[N];int f[N][N],q[N];int main(){    set(trade)    n=read();maxp=read();w=read();    for(int i=1;i<=n;i++) AP[i]=read(),BP[i]=read(),AS[i]=read(),BS[i]=read();    memset(f,-0x3f,sizeof f);    for(int i=1;i<=n;i++){        for(int j=0;j<=AS[i];j++) f[i][j]=-AP[i]*j;        for(int j=0;j<=maxp;j++) f[i][j]=max(f[i][j],f[i-1][j]);        int d=i-w-1;        if(d>=0){            int h=0,t=0;            for(int j=0;j<=maxp;j++){                while(h<t&&q[h]<j-AS[i]) h++;                while(h<t&&f[d][j]+j*AP[i]>=f[d][q[t-1]]+q[t-1]*AP[i]) t--;                q[t++]=j;                if(h<t) f[i][j]=max(f[i][j],f[d][q[h]]-(j-q[h])*AP[i]);            }            h=0,t=0;            for(int j=maxp;j>=0;j--){                while(h<t&&q[h]>j+BS[i]) h++;                while(h<t&&f[d][j]+j*BP[i]>=f[d][q[t-1]]+q[t-1]*BP[i]) t--;                q[t++]=j;                if(h<t) f[i][j]=max(f[i][j],f[d][q[h]]+(q[h]-j)*BP[i]);            }            }    }    for(int i=0;i<=maxp;i++) ans=max(ans,f[n][i]);    printf("%d\n",ans);    return 0;}/*zjk‘s 60分 #include<cstdio>#include<iostream>#include<cstring>#define N 2010using namespace std;int ap[N],bp[N],as[N],bs[N],f[N][N],n,m,w;int main(){    freopen("trade.in","r",stdin);    freopen("trade.out","w",stdout);    scanf("%d%d%d",&n,&m,&w);    for(int i=1;i<=n;i++) scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);    memset(f,-127/3,sizeof(f));    for(int i=1;i<=n;i++)        for(int j=0;j<=as[i];j++)            f[i][j]=-j*ap[i];    for(int i=1;i<=n;i++){        for(int j=0;j<=m;j++){            f[i][j]=max(f[i][j],f[i-1][j]);            for(int k=1;k<=i-w-1;k++){                //买入                for(int l=max(j-as[i],0);l<=j-1;l++)                    f[i][j]=max(f[i][j],f[k][l]-(j-l)*ap[i]);                //卖出                 for(int l=j+1;l<=min(j+bs[i],m);l++)                    f[i][j]=max(f[i][j],f[k][l]+(l-j)*bp[i]);            }        }    }    printf("%d",max(f[n][0],0));    return 0;}*//*30+10暴力dp #include<cstdio>#include<cstring>#include<iostream>#define set(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}const int N=2001;int n,maxp,w,ans,AP[N],BP[N],AS[N],BS[N];int f[N][N][2];//1/0 have traded or notint dfs(int cur,int num,bool d){    int &res=f[cur][num][d];    if(~res) return res;    res=0;    if(cur>=n) return res;    for(int i=(d?cur+w+1:cur+1);i<=n;i++){        res=max(res,dfs(i,num,0));        for(int j=1;j<=(maxp-num,AS[i]);j++){            res=max(res,dfs(i,num+j,1)-j*AP[i]);        }        for(int j=1;j<=min(num,BS[i]);j++){            res=max(res,dfs(i,num-j,1)+j*BP[i]);        }    }    return res;}void dp(){    for(int i=n-1,t;~i;i--){        for(int j=0;j<=maxp;j++){            for(int d=0;d<2;d++){                for(int k=(d?i+w+1:i+1);k<=n;k++){                    int &res=f[i][j][d];                    res=max(res,f[k][j][0]);                    for(int h=1;h<=min(maxp-j,AS[k]);h++){                        res=max(res,f[k][j+h][1]-h*AP[k]);                    }                    for(int h=1;h<=min(j,BS[k]);h++){                        res=max(res,f[k][j-h][1]+h*BP[k]);                    }                }            }        }    }}int main(){    set(trade);    n=read();maxp=read();w=read();    for(int i=1;i<=n;i++) AP[i]=read(),BP[i]=read(),AS[i]=read(),BS[i]=read();    if(n<=50&&maxp<=50) dp();    else{        memset(f,-1,sizeof f);        dfs(0,0,0);    }    printf("%d\n",f[0][0][0]);    return 0;}*/

 

1855: [Scoi2010]股票交易[单调队列优化DP]