题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1855
$f[i][j]$ 表示在第 $i$ 天，拥有 $j$ 股，赚的钱最多是多少。
初始化 $DP$ 数组，分为两种情况：
- $j \leq a_s$ 什么都不买或者只在当天购买： $f[i][j]=max(f[i-1][j],-a_p j)$
- $j > a_s$ 超过了当天购买上限，只能什么都不买： $f[i][j]=f[i-1][j]$
DP转移方程就是（以买入股票举例）： $f[i][j]=max(f[i-w-1][k]-a_p(j-k))$ $k<j$
然后变换一下这个DP式： $f[i][j]=max(f[i-w-1][k]-a_p j+a_p k)$
单调队列中存的是 $(k,f[i-w-1][k]+a_p k)$ 这个二元组，对于第二维单调递减，这样我们每次从队首转移就是最优的，转移之前需要把不合法的： $k+a_s<j$ 这样的从队首删除。
卖出股票和买入非常相似。
答案就是 $max(f[i][0])$ ，因为把所有的股票全卖出去一定最优。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<bits/stdc++.h> #define maxn 2020 #define inf 0x3f3f3f using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int num,val; node(int x=0,int y=0){num=x,val=y;} }; node q[maxn]; int f[maxn][maxn]; int n,m,w,ans; inline void init(){ n=rd(),m=rd(),w=rd(); memset(f,-inf,sizeof f); ans=-inf; } inline void work(){ for(int i=1; i<=n; i++){ int ap=rd(),bp=rd(),as=rd(),bs=rd(); for(int j=0; j<=as; j++)f[i][j]=-ap*j; for(int j=0; j<=m; j++)f[i][j]=max(f[i][j],f[i-1][j]); int k=i-w-1; if(k>=0){ int l=1,r=0; for(int j=0; j<=m; j++){ while(l<=r && q[l].num+as<j)l++; while(l<=r && q[r].val<=f[k][j]+ap*j)r--; q[++r]=node(j,f[k][j]+ap*j); if(l<=r)f[i][j]=max(f[i][j],q[l].val-ap*j); } l=1,r=0; for(int j=m; j>=0; j--){ while(l<=r && q[l].num-bs>j)l++; while(l<=r && q[r].val<=f[k][j]+bp*j)r--; q[++r]=node(j,f[k][j]+bp*j); if(l<=r)f[i][j]=max(f[i][j],q[l].val-bp*j); } } ans=max(ans,f[i][0]); } printf("%d\n",ans); } int main(){ init(); work(); return 0; } |
