bzoj 1855: [Scoi2010]股票交易 单调队列优化dp

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1855


$f[i][j]$ 表示在第 $i$ 天,拥有 $j$ 股,赚的钱最多是多少。

初始化 $DP$ 数组,分为两种情况:

  1.  $j \leq a_s$ 什么都不买或者只在当天购买: $f[i][j]=max(f[i-1][j],-a_p j)$
  2.  $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])$ ,因为把所有的股票全卖出去一定最优。

 

发表评论