首页 > 代码库 > 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 }
Hdu3401(dp+单调队列)