【题解】[SCOI2010]股票交易-白红宇

【题解】[SCOI2010]股票交易

阅读量：4947 次

发布时间：2019-06-11

本文共 2132 字，大约阅读时间需要 7 分钟。

十分普通的DP+不平凡的转移

这道题状态十分明显。转移是$O(n^4)$的，过不去，我们需要优化。

一个十分显然的DP是$f(i,j)$表示第$i$天时候拥有$j$单位股票的最大收益。(可以小于零)。它的转移方式是：

$f(i,j)=max(f(k,b)+(b-j) \times sell[t] or(buy[t]))$

此时，我们发现一个转移需要两重循环，也就是$O(n^2)$，加上右边的式子，就是$O(n^4)$的。

考虑优化：

对于转移方程，发现我们可以进行参变量分离。对状态转移方程进行代数变形。

- $RHS=max(f(k,b)+b \times sell[t]-j \times sell[t])$

- $j$在转移时，是最开始那个等式的$LHS$，可以提前确定，从$max$拿出来。

- $RHS=max(f(k,b)+b \times sell[t])-j\times sell[t]$

- 于是，对于$max(f(k,b)+b \times sell[t])$，可以拿数据结构维护了。

对于转移方法，我们只需要从$f(i-W-1,j) , j\le maxP$转移过来就好了。这一定是最优的那个状态，比它要早的状态一定会$\le f(i-W-1,j) $。

- 因为这个（晚的）状态在转移的时候，考虑过从比他 (早的) 状态直接转移过来，于是$f(i-W-1,j)$不小于前面那个。

于是，我们可以将$f(i-W-1,b) ,b\le maxP$的所有状态压入某个数据结构。我们发现，对于这种数据结构的要求是：

维护最大值

可以清理过期状态（买入卖出股票有多少限制）

重置方便

就是单调队列吃饭的本领。

一句话解释单调队列：一个状态比你小（限制条件少）还比你强（数值大），那么你就被淘汰了。

单调队列是$O(n)$的，枚举$LHS$的$i$是$O(n)$的。总复杂度$O(n^2)$，可以过了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   using namespace std;#define RP(t,a,b) for(register ll (t)=(a),edd_=(b);t<=edd_;++t)#define DRP(t,a,b) for(register ll (t)=(a),edd_=(b);t>=edd_;--t)#define ERP(t,a) for(int t=head[a];t;t=e[t].to)#define Min(a,b) ((a)<(b)?(a):(b))#define TMP template
                   
                    typedef long long ll;TMP inline ccf qr(ccf k){ char c=getchar(); ccf x=0; int q=1; while(c<48||c>57) q=c==45?-1:q,c=getchar(); while(c>=48&&c<=57) x=x*10+c-48,c=getchar(); if(q==-1) x=-x; return x;}const int maxn=2e3+15;inline void Swap(ll& a,ll& b){ ll k=a; a=b; b=k;}ll buy[maxn];ll sell[maxn];ll buytimes[maxn];ll selltimes[maxn];ll n,maxP,W;ll dp[maxn][maxn];int q[maxn];TMP inline ccf Max(ccf a,ccf b){ if(a
                    
                     0){ //trade DRP(i,maxP,0){ while(head<=tail&&q[head]>i+selltimes[t]) head++; while(head<=tail&& dp[t-W-1][q[tail]]+1ll*q[tail]*sell[t] <=dp[t-W-1][i]+1ll*i*sell[t] ) --tail; q[++tail]=i; if(head<=tail) dp[t][i]=max(dp[t][i],dp[t-W-1][q[head]]+(q[head]-i)*sell[t]*1ll); } //purchase head=1,tail=0; RP(i,0,maxP){ while(head<=tail&&q[head]