题面：

题解：

F[i][j]表示前i天，目前手中有j股的最大收入

Case 1:第i天是第一次购买股票

F[i][j]=-j*AP[i]; (1<=j<=AS[i])

Case 2:第i天没有购买股票

F[i][j]=max(F[i][j],F[i-1][j])

Case 3:第i天买入j-k股

因为F[i][j]的最优情况是会顺承的，所以如果

第i天有交易的话，直接从第i-W-1天进行转移即可

F[i][j]=max(F[i][j],F[i-W-1][k]-AP[i]*(j-k))

(1<=j-k<=AS[i],i-W-1>=1)

Case 4:第i天卖出k-j股

F[i][j]=max(F[i][j],F[i-W-1][k]+BP[i]*(k-j))

(1<=k-j<=BS[i],i-W-1>=1)

再使用单调队列进行维护

所以对于Case 3:

找出max(F[i-W-1][k]+AP[i]*k)-AP[i]*j (1<=j-k<=AS[i],i-W-1>=1)

j-AS[i]<=k<=j-1,i-W-1>=1

对于Case 4:

找出max(F[i-W-1][k]+BP[i]*k)-BP[i]*j (1<=j-k<=BS[i],i-W-1>=1)

1+j<=k<=BS[i]+j,i-W-1>=1

 

额外：鸣谢@QZZ帮我解答了一个傻逼问题。

代码：

1 #include
     
       2 #include
      
        3 #define min(a,b) ((a)<(b)?(a):(b)) 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 using namespace std; 6 const int maxn=2050,inf=1<<30; 7 int T,MaxP,W,F[maxn][maxn],AP[maxn],BP[maxn],AS[maxn],BS[maxn]; 8 struct Node{ int k,data; }nd; 9 Node que[maxn];10 int f1,f2,ans;11 int main(){12     scanf("%d%d%d",&T,&MaxP,&W);13     for(int i=1;i<=T;i++)14         scanf("%d%d%d%d",&AP[i],&BP[i],&AS[i],&BS[i]);15        for(int i=0;i<=T;i++)16         for(int j=0;j<=MaxP;j++){17             if(j<=AS[i]) F[i][j]=-j*AP[i];18             else F[i][j]=-inf;19         }20     for(int i=1;i<=T;i++){21         for(int j=0;j<=MaxP;j++) F[i][j]=max(F[i][j],F[i-1][j]);22         if(i-W-1>=0){23             int w=i-W-1;24             f1=1;f2=0;25             for(int j=0;j<=MaxP;j++){                26                 while(f1<=f2 && que[f1].k
       
        =que[f2].data) f2--;29                 que[++f2].k=j; que[f2].data=F[w][j]+AP[i]*j;30             }31             f1=1;f2=0;32             for(int j=MaxP;j>=0;j--){                33                 while(f1<=f2 && que[f1].k>j+BS[i]) f1++;34                 if(f1<=f2) F[i][j]=max(F[i][j],que[f1].data-BP[i]*j);35                 while(f1<=f2 && F[w][j]+BP[i]*j>=que[f2].data) f2--;36                 que[++f2].k=j; que[f2].data=F[w][j]+BP[i]*j;37             }38         }39     }40     ans=-inf;41     for(int i=0;i<=MaxP;i++) ans=max(ans,F[T][i]);42     printf("%d\n",ans);43     return 0;44 }
       
      
     

---

By:AlenaNuna