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

题解- P2569 股票交易

题目意思

由于题面过长，不再描述。
戳这里
$Sol$

这道题目想清楚后还是不难的，是一道不错的单调队列练习题。

首先我们要明确状态：

$f_{i,j}$ 表式到第 $i$ 天拥有 $j$ 个股票的最大收益。

这个状态还是挺显然的，不像某些题目卡状态。

对于转移，要分成多种情况来考虑：

$(I)$ 我们就是没有任何积蓄的情况下买（相当于一个初始化），此时转移显然

$f_{i,j}=-j \times AP_i$ $(j\leq MaxP)$

$(II)$ 我们当天选择不买也不买

$f_{i,j}=\max [f_{i-1,j},f_{i,j}]$

这个应该比较好理解就是继承原来的最大收益。

$(III)$ 已经有资金基础下买股票,此时如何转移呢？

我们考虑上次买有多少股票 $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$ 。所以这次转移是这样的。**

$(IV)$ 已经有资金基础下卖股票,此时如何转移呢？

我们考虑上次买有多少股票 $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;
}