首页 > 代码库 > Hdu3401(dp+单调队列)

Hdu3401(dp+单调队列)

题目大意:

一个人有T元,最大可以持有的股票数量是maxp,交易必须隔w天进行.告诉每天可以买股票的数量和买入价格,以及每天可以卖出股票的数量和卖出价格,问最后最大的收益是多少.

思路:

状态可以定义为:f[i][j]第i天,手持j股且完成当天的操作的最大收益.考虑这一天的操作,一共有三种,(1)什么都不做,(2)在这一天,有一次卖出交易,(3)在这一天,有一次买入交易.那么也就是f[i][j]=max(f[i-1][j],f[i-w-1][k]+(j-k)*Bpi,f[i-w-1][k]-(k-j)*Api)

两个疑问.

第一,为什么在当前天只考虑跟这天恰好隔w天的,相隔最少是w天,也有可能相隔为w+x天啊.那么假设我们考虑相隔w,w+1,w+2,w+3...的这些天,那么实际上考虑了w+1天的时候就已经考虑了这一天什么都不做的形式了,也就是说已经考虑了f[i-1][j]的形式了,所以在每一天都考虑f[i-1][j]的话,就不需要考虑每一个大于w的间隔.因为已经考虑过了.

第二,这样看来状态数是O(2000*2000) ,而转移数(枚举k)是O(2000),整体复杂度为(8*10^9) 不能接受.如何优化?如果可以在O(1)的时间内找到最大的买入卖出的状态的话就可以接受了.对状态进行变形.f[i-w-1][k]+(j-k)*Bpi=f[i-w-1][k]-k*Bpi+j*Bpi.针对给定的要求状态f[i][j],后面的j*Bpi是一个常数,而前面的f[i-w-1][k]-k*Bpi前一维i-w-1针对一个给定的i是一个常量,后一维k是小于j的数.那么如果能快速求出f[i-w-1][k]-k*Bpi的最大值就ok了.因为只要i确定,i-w-1就唯一确定,而且求解的顺序是一定的,那么如果现在的i确定了,我们判断它是否大于w+1,如果大于,也就是说,我们在枚举每一个j的过程中都会用到f[i-w-1][k] (k<j).在和j并列的地方先枚举k,同时用单调队列维护最大值,然后在枚举j,过程中单调队列平摊O(1)的复杂度可以快速的给出对于一个指定的j相应的那个k使得f[i-w-1][k]最大.

AC代码.

 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 #define maxn 2010 6 #define INF 0x7fffffff 7 struct node{ 8    int x; //单调队列的dp[i-w-1][k]+APi[i]*k或dp[i-w-1][k]+BPi[i]*k 9    int p; //持股数10 }que[maxn],temp;11 int s,e,dp[maxn][maxn];12 int main()13 {14     //freopen("in.txt","r",stdin);15     int Api[maxn],Bpi[maxn],Asi[maxn],Bsi[maxn],T,Maxp,W,t,res;16     int i,j;17     scanf("%d",&t);18     while(t--)19     {20         res=-INF;21         scanf("%d%d%d",&T,&Maxp,&W);22         for(i=1;i<=T;i++)23          scanf("%d%d%d%d",&Api[i],&Bpi[i],&Asi[i],&Bsi[i]);24         for(i=0;i<=T;i++)25          for(j=0;j<=Maxp;j++)26           dp[i][j]=-INF;27         for(i=1;i<=W+1;i++)28          for(j=0;j<=Asi[i];j++)29           dp[i][j]=-Api[i]*j;30         for(i=2;i<=T;i++)31         {32          for(j=0;j<=Maxp;j++)33            dp[i][j]=max(dp[i][j],dp[i-1][j]);34          if(i<=W+1) continue;35          //买入36          s=e=1;37          for(j=0;j<=Maxp;j++)38          {39             temp.x=dp[i-W-1][j]+j*Api[i];40             temp.p=j;41             for(;s<e&&que[e-1].x<temp.x;e--);42             que[e++]=temp;43             for(;s<e&&que[s].p+Asi[i]<j;s++);44             dp[i][j]=max(dp[i][j],que[s].x-Api[i]*j);45          }46          //卖出47          s=e=1;48          for(j=Maxp;j>=0;j--)49          {50             temp.x=dp[i-W-1][j]+j*Bpi[i];51             temp.p=j;52             for(;s<e&&que[e-1].x<temp.x;e--);53             que[e++]=temp;54             for(;s<e&&que[s].p-Bsi[i]>j;s++);55             dp[i][j]=max(dp[i][j],que[s].x-Bpi[i]*j);56          }57         }58         for(i=0;i<=Maxp;i++)59          res=max(res,dp[T][i]);60         cout<<res<<endl;61     }62     return 0;63 }
View Code

 

Hdu3401(dp+单调队列)