SCOI2010——股票交易（单调队列DP）

1855: [Scoi2010]股票交易

Time Limit: 5 Sec Memory Limit: 64 MB

Submit: 491 Solved: 209

[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

解析：

f[i][j]表示第i天结束时，还有j只股票的收益

很容易想到朴素的DP方程：f[i][j] = max{f[i - 1][j],f[i - W - 1][j - k1] - ap[i] * k1,f[i - W - 1][j + k2] + bp[i] * k2}。

令t = i - W - 1，p = j - k1, q = j + k2。
忽略f[i - 1][j]项，则有：

f[i][j] = max{f[t][p] - ap[i] * (j - p),f[t][q] + bp[i] * (q - j) }，且p >= j - as[i], q <= j + bs[i]。

即f[i][j] = max(f[t][p] + ap[i] * p - ap[i] * j, f[t][q] + bp[i] * q - bp[i] * j}。

由此想到用单调队列。。。

代码：

/**************************************************************
    Problem: 1855
    User: jianing
    Language: C++
    Result: Accepted
    Time:460 ms
    Memory:16604 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2010;
 
int T,MaxP,w,as,bs,ap,bp;
int dp[N][N];
int q[N];
int val[N];
 
void work()
{
    scanf("%d%d%d",&T,&MaxP,&w);
    int st,ed;       int ans=-1;
    memset(dp,0xc0,sizeof(dp));
    for(int i=1;i<=T;i++)//第i天
    {
        scanf("%d%d%d%d",&ap,&bp,&as,&bs);//买入价，卖出价，买入股票数，卖出股票数
        for(int j=0;j<=as;j++)dp[i][j]=-ap*j;//赋初值
        for(int j=0;j<=MaxP;j++)             //考虑不进行交易的情况
            dp[i][j]=max(dp[i-1][j],dp[i][j]);
        int t=i-w-1; //上次交易是第t天
        if(t>=0)
        {
            st=ed=0;
            for(int j=0;j<=MaxP;j++)//每次交易的股票数
            {
                while(st<ed && q[st]<j-as)st++;//不满足q[st]>=j-as就出队
                while(st<ed && dp[t][j]+ap*j>=val[ed-1])ed--;//用val数组存队列元素收益
                val[ed]=dp[t][j]+j*ap;
                q[ed++]=j;
                if(st<ed)dp[i][j]=max(dp[i][j],val[st]-j*ap);
            }//第t天到第i天买入股票
            st=ed=0;
            for(int j=MaxP;j>=0;j--)
            {
                while(st<ed && q[st]>j+bs)st++;//满足q[st]<=j+bs
                while(st<ed && dp[t][j]+bp*j>=val[ed-1])ed--;
                val[ed]=dp[t][j]+j*bp;
                q[ed++]=j;
                if(st<ed)dp[i][j]=max(dp[i][j],val[st]-j*bp);
            } //卖出股票
        }
        ans=max(ans,dp[i][0]);
    }
    printf("%d\n",ans);
}
 
int main()
{
   // freopen("trade.in","r",stdin);
   // freopen("trade.out","w",stdout);
    work();
    return 0;
}

更多精彩内容