题目描述
在 $N$ 天内每隔 $M$ 天可以进行一次股票交易,每次交易可以买入或卖出。每天持股数有一定限制,每天买入、卖出的股票数和股票购价、售价均不同,需要最大化最后一天的收益。
解法
从最朴素的算法开始考虑:设 $f_{i,j,k=0/1}$ 表示在第 $i$ 天持股数为 $j$,当天进行操作为买/卖时收益的最大值。
可以发现最后一维没有实际用处,因此可以去掉。
那么状态转移方程就非常明显了。
初始化(当天刚刚开始购买股票,之前持股数为 $0$,最大收入为花费的成本):$$f_{i,j}=-AP_i*j\space(0\leq j\leq AS_i)$$
若当天不进行交易:$$f_{i,j}=max\{f_{i,j},f_{i-1,j}\}$$
若当天进行买入操作:$$f_{i,j}=max\{f_{i,j},f_{i’,j’}-(j-j’)\times AP_i\}\space(i’\in[1,i-M-1],0\leq j-j’\leq AS_i)$$
若当天进行卖出操作:$$f_{i,j}=max\{f_{i,j},f_{i’,j’}+(j’-j)\times BP_i\}\space(i’\in[1,i-M-1],0\leq j’-j\leq BS_i)$$
我们需要两重循环分别枚举 $i,j$,一重循环枚举 $i’$,一重循环枚举 $j’$,总时间复杂度为 $O(T^2MaxP^2)$。
这样的算法显然不够优秀。考虑优化。
我们发现,在上述方程中,既然 $i’\in[1,i-M-1]$,那么当我们处理 $f_{i,j}$ 时,这个区间的最优解一定被保存在 $f_{i-M-1,j’}$ 中。
因此直接令 $i’=i-M-1$,算法复杂度优化至 $O(TMaxP^2)$。
这个复杂度仍然无法令我们满意。因此考虑进一步的优化。
在上一步的优化中,我们省略了对 $i’$ 的枚举。接下来我们在 $j’$ 上做工作。
将最初得到的后两个方程拆开,得到:
买入:$$f_{i,j}=max\{f_{i,j},f_{i’,j’}+j’\times AP_i\}-j\times AP_i\space(i’\in[1,i-M-1],0\leq j-j’\leq AS_i)$$
卖出:$$f_{i,j}=max\{f_{i,j},f_{i’,j’}+j’\times BP_i\}-j\times BP_i\space(i’\in[1,i-M-1],0\leq j’-j\leq BS_i)$$
可以发现,在这两个方程中,当 $j$ 确定时,$max$ 外的部分是一个定值。对于 $max$ 内的部分,我们可以使用单调队列进行维护,并在 $O(1)$ 的时间内得到其最大值。
经过上述优化,算法复杂度降为$O(TMaxP)$,能够通过本题。
对于最后的答案,扫描 $f_{T,i}\space(i\in[0,MaxP])$ 并取最大值即可。
问题已经解决完毕,但一些完美主义者或许并不满足于取答案时冗余的扫描方式。因此本篇题解提供一个小技巧:容易证明,在最后一天,把手中的股票都售出当然最好——否则手中剩余的股票就成了对成本的浪费。既然如此,最后的答案一定是 $f_{T,0}$。
需要注意的一点是,在算法开始前,$f$ 数组中所有元素值应设为 $-\infty$ 而非 $0$。
C++ 代码
#include<cstdio>
int f[2020][2020],n,mp,m,ap[2020],bp[2020],as[2020],bs[2020],lday,ans;
struct monotone_queue{
int a[2020],h,t;
monotone_queue(){h=1;t=0;}
int front(){return a[h];}
int back(){return a[t];}
bool empty(){return h>t;}
bool size(){return t-h+1;}
bool clear(){h=1;t=0;return true;}
bool pop_front(){if(!empty())h++;return true;}
bool pop_back(){if(!empty())t--;return true;}
bool push(int x){a[++t]=x;return true;}
}q;
int Max(int a,int b){return a>b?a:b;}
int main(){
scanf("%d%d%d",&n,&mp,&m);
for(int i=1;i<=n;i++)
scanf("%d%d%d%d",ap+i,bp+i,as+i,bs+i);//买价 卖价 买数 卖数
for(int i=1;i<=mp;i++)
f[0][i]=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
q.clear();
lday=i-m-1;
for(int j=0;j<=mp;j++){
if(j<=as[i])f[i][j]=-ap[i]*j;//当前刚开始买,最优收入设为失去的成本
else f[i][j]=-0x3f3f3f3f;
f[i][j]=Max(f[i][j],f[i-1][j]);//注意这句话的位置,这里容易写错
}
if(i<=m)continue;
for(int j=0;j<=mp;j++){//买入
while(q.front()<j-as[i]&&!q.empty())q.pop_front();
if(!q.empty())f[i][j]=Max(f[i][j],f[lday][q.front()]+ap[i]*q.front()-ap[i]*j);
while(f[lday][q.back()]+ap[i]*q.back()<=f[lday][j]+ap[i]*j&&!q.empty())q.pop_back();
q.push(j);
}
q.clear();
for(int j=mp;j>=0;j--){//卖出
while(q.front()>j+bs[i]&&!q.empty())q.pop_front();
if(!q.empty())f[i][j]=Max(f[i][j],f[lday][q.front()]+bp[i]*q.front()-bp[i]*j);
while(f[lday][q.back()]+bp[i]*q.back()<=f[lday][j]+bp[i]*j&&!q.empty())q.pop_back();
q.push(j);
}
}
printf("%d",f[n][0]);
}
呃呃呃所以为什么这会是道简单题e
$\Pi$
%%%%%yyqTQL
题本身思路想起来还是比较顺利的,但是代码里要注意的细节有点多