DP/单调队列优化

　　题解：http://www.cnblogs.com/jianglangcaijin/p/3799736.html

　　令f[i][j]表示第 i 天结束后，手里剩下 j 股的最大利润，则有：

　　　　\[ f[i][j]= \begin{cases}　f[i-1][j] & &{(不买不卖)}\\ f[i-w-1][k]-ap[i]*(j-k)& &{ j-as[i] \leq k \leq j-1 (买入)}\\ f[i-w-1][k]+bp[i]*(k-j)& &{ j+1 \leq k \leq j+bs[i] (卖出)} \end{cases} \]

　　对于买入，我们将式子变形得到：

　　　　$$ f[i][j]=f[i-w-1][k]+ap[i]*k-ap[i]*j $$

　　我们知道单调队列优化可以将形如 $ f[i]=max/min \{ f[k] \}+g[i] $ 的式子中对k的枚举利用队列进行优化，这个式子中，"f[k]" 即是 $ f[i-w-1][k]+ap[i]*k $，“g[i]”即是 $ -ap[i]*j $，所以我们在枚举 j 的同时即可完成对k的维护（即每个f[i]都是一次单调队列优化下的DP）

　　而卖出同理。

 /**************************************************************

     Problem: 1855

     User: Tunix

     Language: C++

     Result: Accepted

     Time:380 ms

     Memory:17068 kb

 ****************************************************************/

 //BZOJ 1855

 #include<cmath>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

     return v*=sign;

 }

 const int N=,INF=~0u>>;

 typedef long long LL;

 /******************tamplate*********************/

 struct node{

     int x,y;

     node(int _=,int __=):x(_),y(__){}

 }q[N];

 int f[N][N];

 int main(){

 #ifndef ONLINE_JUDGE

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

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

 #endif

     int n=getint(),m=getint(),w=getint();

     F(i,,n) F(j,,m) f[i][j]=-INF;

     int ans=,ap,bp,as,bs;

     F(i,,n){

         ap=getint(); bp=getint(); as=getint(); bs=getint();

         F(j,,as) f[i][j]=-ap*j;

         F(j,,m) f[i][j]=max(f[i][j],f[i-][j]);

         int k=i-w-;

         if (k>=){

             int st=,ed=;

             F(j,,m){

                 while(st<ed && q[st].x<j-as) st++;

                 while(st<ed && q[ed-].y<=f[k][j]+ap*j) ed--;

                 q[ed++]=node(j,f[k][j]+ap*j);

                 if (st<ed) f[i][j]=max(f[i][j],q[st].y-ap*j);

             }

             st=ed=;

             D(j,m,){

                 while(st<ed && q[st].x>j+bs) st++;

                 while(st<ed && q[ed-].y<=f[k][j]+bp*j) ed--;

                 q[ed++]=node(j,f[k][j]+bp*j);

                 if (st<ed) f[i][j]=max(f[i][j],q[st].y-bp*j);

             }

         }

         ans=max(ans,f[i][]);

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

【BZOJ】【1855】【SCOI2010】/【HDOJ】【3401】股票交易

DP/单调队列优化

最新文章

热门文章