随便's Blog

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

 

动规，对于f(i,j)表示第i天有j张股票的最大钱数。

转移方式有三种：

                           f(i,j)=f(i-1,j)（不买不卖）

                           f(i,j)=f(i-w,k)-(k-j)*ap(买入）=》f(i-w,k)-k*ap+j*ap

                           f(i,j)=f(i-w,k)+(j-k)*bp（卖出）=》f(i-w,k)-k*bp+j*bp

                        对于  f(i-w,k)-k*ap  可以用一个优先队列维护于是就可以O（1）求出来；

 

/**************************************************************
    Problem: 1855
    User: 1115825064
    Language: C++
    Result: Accepted
    Time:376 ms
    Memory:16976 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
const int N=2004,INF=0x3fffffff;
int t,maxp,w,f[N][N];
struct D{
    int x,y;
}q[N];
int head,tail;
int ans=0;
int main()
{
    //freopen("1.txt","r",stdin);
     
    scanf("%d%d%d",&t,&maxp,&w);
    for(int i=0;i<=t;++i)
        for(int j=0;j<=maxp;++j)
            f[i][j]=-INF;
    for(int i=1;i<=t;++i)
    {
        int ap,bp,as,bs,bj=0;
        scanf("%d%d%d%d",&ap,&bp,&as,&bs);
        for(int j=0;j<=as;++j)
            f[i][j]=-ap*j;
        for(int j=0;j<=maxp;++j)
            f[i][j]=max(f[i][j],f[i-1][j]);
        int k=i-w-1;
        if(k>=0)
        {
             head=0,tail=0;
             for(int j=0;j<=maxp;++j)
             {
                while(q[head].x<j-as&&head<tail) head++;
                while(q[tail-1].y<=f[k][j]+ap*j&&head<tail) tail--;
                q[tail].x=j,q[tail++].y=f[k][j]+ap*j;
                if(head<tail) f[i][j]=max(f[i][j],q[head].y-ap*j);
             }
             head=0,tail=0; 
             for(int j=maxp;j>=0;--j)
             {
                while(head<tail&&q[head].x>j+bs) head++;
                while(head<tail&&q[tail-1].y<=f[k][j]+bp*j)tail--;
                q[tail].x=j,q[tail++].y=f[k][j]+bp*j;
                if(head<tail) f[i][j]=max(f[i][j],q[head].y-bp*j);
             }
        }
        ans=max(ans,f[i][0]);
    }
    printf("%d",ans);
    return 0;
}