题解 P2569 【[SCOI2010]股票交易】

奇米 · 2020-02-16 17:47:00 · 题解

题解- P2569 股票交易

题目意思

由于题面过长，不再描述。戳这里
Sol
这道题目想清楚后还是不难的，是一道不错的单调队列练习题。

首先我们要明确状态：
这个状态还是挺显然的，不像某些题目卡状态。对于转移，要分成多种情况来考虑： $(I)$ 我们就是没有任何积蓄的情况下买（相当于一个初始化），此时转移显然 $f_{i,j}=-j \times AP_i $ $(j\leq MaxP) $f_{i,j}=\max [f_{i-1,j},f_{i,j}]
这个应该比较好理解就是继承原来的最大收益。
我们考虑上次买有多少股票$k$，则转移很显然： $f_{i,j}=\max [f_{i-w-1,k}-(j-k) \times AP_i,f_{i,j}]
如何理解呢？就是上次购买时间为(i-w-1)，间隔w天买嘛。且因为这次是买进，数量要比上次多，的所以k\leq j。所以这次转移是这样的。
我们考虑上次买有多少股票$k$，则转移很显然： $f_{i,j}=\max [f_{i-w-1,k}+(k-j) \times BP_i,f_{i,j}]
如何理解呢（和III同理)？就是上次购买时间为(i-w-1)，间隔w天买嘛。且因为这次是卖出，数量要比上次少，的所以j\leq k。所以这次转移是这样的。

但是这样的时间复杂度是存在问题的，大概为O(T \times MaxP^2)，可以获得50分的好成绩。我们考虑优化，单调队列？线段树？

此时我们可以发现转移符合单调性优化原则，所以可以用单调队列来优化。对于(III),(IV)情况我们就像滑动窗口一样做。只要做(III)的时候正着扫，(IV)时候到这做（因为卖出去，上次股票肯定比这次多）。应该比较好理解吧。

这里还有一个显而易见的优化：就是如果现在的天数\leq w是不用做(III),(IV)的。

这样复杂度就变为O(T \times MaxP)，可以轻松过掉这道题目。
Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read()
{
    int sum=0,ff=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

const int N=2005;

int T,MP,W,AP[N],BP[N],AS[N],BS[N],ans;
int f[N][N],q[N];

inline int max(int i,int j)
{
    return (i>j)?i:j;
}

signed main()
{
    T=read();
    MP=read();
    W=read();
    for ( int i=1;i<=T;i++ )
    {
        AP[i]=read();
        BP[i]=read();
        AS[i]=read();
        BS[i]=read();
    }
    memset(f,-63,sizeof(f));
    for ( int i=1;i<=T;i++ ) 
    {
        for ( int j=0;j<=AS[i];j++ ) 
            f[i][j]=-1ll*j*AP[i];
        for ( int j=0;j<=MP;j++ ) 
            f[i][j]=max(f[i][j],f[i-1][j]);
        if(i<=W) continue;
        int head=1,tail=0;
        for ( int j=0;j<=MP;j++ )
        {
            while(head<=tail && q[head]<j-AS[i]) head++;
            while(head<=tail && f[i-W-1][q[tail]]+q[tail]*AP[i]<=f[i-W-1][j]+j*AP[i]) tail--;
            q[++tail]=j;
            if(head<=tail) 
                f[i][j]=max(f[i-W-1][q[head]]-(j-q[head])*AP[i],f[i][j]);
        }
        head=1,tail=0;
        for ( int j=MP;j>=0;j-- )
        {
            while(head<=tail && q[head]>j+BS[i]) head++;
            while(head<=tail && f[i-W-1][q[tail]]+q[tail]*BP[i]<=f[i-W-1][j]+j*BP[i]) tail--;
            q[++tail]=j;
            if(head<=tail) 
                f[i][j]=max(f[i-W-1][q[head]]+(q[head]-j)*BP[i],f[i][j]);
        }
    }
    ans=-1e12;
    for ( int i=0;i<=MP;i++ ) ans=max(ans,f[T][i]);
    printf("%lld\n",ans);
    return 0;
}