【题解】[SCOI2010]股票交易

十分普通的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<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<bitset>

#include<vector>

#include<map>

#include<ctime>

#include<cstdlib>

#include<set>

#include<bitset>

#include<stack>

#include<list>

#include<cmath>

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<class ccf>

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<b)

   return b;

   return a;

}

inline void init(){

   memset(dp,-0xf,sizeof dp);

   RP(t,1,n){

   buy[t]=qr(1ll);

   sell[t]=qr(1ll);

   buytimes[t]=qr(1ll);

   selltimes[t]=qr(1ll);

   }

   RP(t,1,n){

   int head=1,tail=0;

   if(t-W-1>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]<i-buytimes[t])

   	    ++head;

   	while(head<=tail&&

   	      dp[t-W-1][q[tail]]+q[tail]*buy[t]

   	      <=dp[t-W-1][i]+i*buy[t])

   	    --tail;

   	q[++tail]=i;

   	if(head<=tail)

   	    dp[t][i]=Max(dp[t][i],dp[t-W-1][q[head]]+(q[head]-i)*buy[t]*1ll);

       }

   }

   //restart

   RP(i,0,maxP){

       dp[t][i]=Max(dp[t][i],dp[t-1][i]);

       if(i<=buytimes[t])

   	dp[t][i]=Max(dp[t][i],-i*buy[t]);

   }

   }

   ll ans=0;

   RP(t,0,maxP)

   ans=max(ans,dp[n][t]);

   cout<<ans<<endl;

}

int main(){

#ifndef ONLINE_JUDGE

   freopen("in.in","r",stdin);

   freopen("out.out","w",stdout);

#endif

   while(~scanf("%lld%lld%lld",&n,&maxP,&W))

   init();

   return 0;

}

巴特西

【题解】[SCOI2010]股票交易

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

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

考虑优化：

最新文章

热门文章