本文移植自个人的原博客（原文）

题目链接

Luogu 2569

题目描述

题目描述

题解

$o(t∗maxp^2)$算法

$o(t∗maxp^2)$算法有70分，还是比较良心的。

这题转移方程也不难想，可以设$dp[i][j]$为第$i$天后手中还剩$t$张股票时的最大收益。但这里有些细节要注意一下，有些情况是无法达到的，比如说第一天只能买$3$张股票，那么$dp[1][4]$是便是无效的，不妨将$dp$数组初始化为极小值，这样没有在转移中赋过值的状态就会在比较中去掉（具体转移方程见下）。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2017;
int n,maxp,w,ap[N],bp[N],as[N],bs[N],dp[N][N];
int main()
{
  scanf("%d%d%d",&n,&maxp,&w);
    for(int i=1;i<=n;++i)scanf("%d%d%d%d",ap+i,bp+i,as+i,bs+i);
  memset(dp,-0x3f,sizeof(dp));
  for(int i=1;i<=n;++i)
  {
      for(int j=0;j<=as[i];++j)dp[i][j]=-ap[i]*j;//表示这些状态是可以达到的，具体的含义为第i天前不做任何操作时，第i天的收益。
      for(int j=0;j<=maxp;++j)
      {
          dp[i][j]=max(dp[i-1][j],dp[i][j]);//该天没有操作
          if(i-w-1>=0)
          for(int k=j+1;k<=min(j+bs[i],maxp);++k)
          dp[i][j]=max(dp[i][j],dp[i-w-1][k]+(k-j)*bp[i]);//卖出
          if(i-w-1>=0)
          for(int k=max(j-as[i],0);k<j;++k)
          dp[i][j]=max(dp[i][j],dp[i-w-1][k]-(j-k)*ap[i]);//买入
      }
  }
  printf("%d",dp[n][0]);
}

$o(t∗maxp)$算法（单调队列）

此题单调队列优化思想不难，但是还要注意各种细节。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2017;
int n,maxp,w,head,tail,ap[N],bp[N],as[N],bs[N],dp[N][N],q[2*N];
int main()
{
    scanf("%d%d%d",&n,&maxp,&w);
    for(int i=1;i<=n;++i)scanf("%d%d%d%d",ap+i,bp+i,as+i,bs+i);
    memset(dp,-0x3f,sizeof(dp));
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=as[i];++j)    dp[i][j]=-ap[i]*j;
        for(int j=0;j<=maxp;++j)    dp[i][j]=max(dp[i][j],dp[i-1][j]);
        if(i-w-1>=0)
        {
            head=1,tail=0;
            for(int j=0;j<=maxp;++j)//买入 
            {
                while(head<=tail&&q[head]<max(0,j-as[i]))head++;
                if(head<=tail)dp[i][j]=max(dp[i][j],dp[i-w-1][q[head]]-(j-q[head])*ap[i]);
                while(head<=tail&&dp[i-w-1][j]+j*ap[i]>=dp[i-w-1][q[tail]]+q[tail]*ap[i])tail--;
                q[++tail]=j;
            }
            head=1,tail=0;
            for(int j=maxp;j>=0;--j)//卖出 
            {
                while(head<=tail&&q[head]>min(maxp,j+bs[i]))head++;
                if(head<=tail)dp[i][j]=max(dp[i][j],dp[i-w-1][q[head]]+(q[head]-j)*bp[i]);
                while(head<=tail&&dp[i-w-1][j]+j*bp[i]>=dp[i-w-1][q[tail]]+q[tail]*bp[i])tail--;
                q[++tail]=j;
            }
        }
    }
    printf("%d",dp[n][0]);
}