【单调队列优化dp】HDU 3401 Trade

时间：2022-12-25 21:31:59

http://acm.hdu.edu.cn/showproblem.php?pid=3401

【题意】

  • 知道之后n天的股票买卖价格（api，bpi），以及每天股票买卖数量上限（asi，bsi），问他最多能赚多少钱。开始时有无限本金，要求任两次交易需要间隔W天以上，即第i天交易，第i+w+1天才能再交易。同时他任意时刻最多只能拥有maxp的股票

【思路】

  • dp[i][j]表示第i天拥有j支股票的最大收益，有三种转移方案：
  • dp[i][j]=max(dp[i][j],dp[i-1][j])表示第i天不买也不卖，由前一天转移而来
  • dp[i][j]=max(dp[i][j],dp[i-w-1][k]-(j-k)*ap[i])表示第i天买股票，有第i-w-1天转移而来
  • dp[i][j]=max(dp[i][j],dp[i-w-1][k]+(k-j)*bp[i])表示第i天卖股票，有第i-w-1天转移而来
  • 注意只需计算由i-w-1天转移而来，因为i-w-1天前的最优值已经通过不买不卖转移到了i-w-1天，即dp[i][j],j固定是随i单调递增的
  • 现在dp的复杂度是n^3,怎样降低复杂度？
  • 分析买股票的情况，dp[i][j]=max(dp[i-w-1][k]+k*ap[i])-j*ap[j],类似a[i]=max(b[k])+c[i]，可以用单调队列优化
  • 我理解的是，状态数为2D,转移为1D,然后又有单调性，可以固定一维状态，把转移均摊到另一维，相当于转移是O(1)的，所以单调队列可以把dp降一维
  • a[i]=max(b[k]),若k<=j是从前往后递推，若k>=j是从后往前递推

【AC】

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=2e3+;

 const int inf=0x3f3f3f3f;

 int ap[maxn],bp[maxn],as[maxn],bs[maxn];

 int n,maxp,w;

 int dp[maxn][maxn];

 struct node

 {

     int x;

     int num;

 }q[maxn];

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         memset(dp,-inf,sizeof(dp));//求最大值，所以初始化为无穷小

         scanf("%d%d%d",&n,&maxp,&w);

         for(int i=;i<=n;i++) scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);

         for(int i=;i<=n;i++) dp[i][]=;//拥有股票为0的最大收益当前是0

         //前w+1天和[w+2,n]要分开算

         //前w+1天只有两种情况：1.每天都不买不卖 2.其中一天买了股票 不能卖股票，而且最多只有一天能交易

         for(int i=;i<=w+;i++)

         {

             for(int j=;j<=as[i];j++)

             {

                 dp[i][j]=-j*ap[i];//可以选择在当天买

             }

         }

         for(int j=;j<=maxp;j++)

         {

             for(int i=;i<=w+;i++)

             {

                 dp[i][j]=max(dp[i][j],dp[i-][j]);//也可以选择由前一天转移而来

             }

         }

         for(int i=w+;i<=n;i++)

         {

             int head=,tail=;

             for(int j=;j<=maxp;j++)

             {

                 dp[i][j]=max(dp[i][j],dp[i-][j]);//不买也不卖

                 //dp[i][j]=max(dp[i-w-1][k]+k*ap[i])-j*ap[i],其中k<=j

                 while(head<=tail&&q[tail].x<=dp[i-w-][j]+j*ap[i]) tail--;

                 q[++tail].x=dp[i-w-][j]+j*ap[i];q[tail].num=j;

                 while(q[head].num+as[i]<j) head++;

                 dp[i][j]=max(dp[i][j],q[head].x-j*ap[i]);

             }

             //dp[i][j]=max(dp[i-w-1][k]+k*bp[i])-j*bp[i],其中k>=j

             head=,tail=;

             for(int j=maxp;j>=;j--)

             {

                 while(head<=tail&&q[tail].x<=dp[i-w-][j]+j*bp[i]) tail--;

                 q[++tail].x=dp[i-w-][j]+j*bp[i];q[tail].num=j;

                 while(q[head].num>bs[i]+j) head++;

                 dp[i][j]=max(dp[i][j],q[head].x-j*bp[i]);

             }

         }

         int ans=;

         for(int i=;i<=maxp;i++)

         {

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

         }

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

     }

     return ;

 }

单调队列优化dp

相关文章