P2569 [SCOI2010] 股票交易

1 . 凭空买

仅本情况下的状态可以直接赋值，其他状态初值为 $-inf$，即：

$f_{i,j}=-ap_i\ \times \ j$$(0 \leqslant j \leqslant as_i)$

下面三种情况，分别可列三个状态转移方程：

2 . 不买也不卖

最好想也最好列转移方程的一种情况，直接由上一天转移，且拥有股票数量不变。即：

$f_{i,j}​=max(f_{i,j}\ ,,\ , f_{i-1,j})$

3 . 在之前的基础上买股票

这里的方程就比较复杂了，这里详细解释一下：

题目中指明说两次交易需要至少隔 $w$ 天。也就是说，今天是第 $i$ 天交易，那么上一次交易最近是在第 $i - w - 1$ 天。

可我第 $i - w - 1$ 天之前也可以交易啊？为什么偏偏是那一天，而不是第 $i - w - 2$ 天？

回看刚刚讨论的第 2 种情况，我们已经把某一天以前的最优答案转移到了该天，所以从那一天转移，相当于从那一天包括前面任何一天开始转移，省去了大把时间。

接下来，我们已知第 $i$ 天拥有 $j$ 张股票，假设第 $i - w - 1$ 天拥有 $k$ 张股票。

$k$ 一定比 $j$ 小，因为这一种情况是买股票，股票只能多。

但股票又不能买太多，限制最多为 $as$ 张。所以 $j - as_i$​ 是底线。

继续，这次交易买了 $j - k$ 张股票，要花去 $(j - k) \times ap_i$ 元。

整理一下，转移方程为：

$f_{i,j}=max(f_{i,j}\ ,,\ ,f_{i-w-1,k}-(j-k)\times ap_i)$

$(j - as_i \leqslant k < j)$

4 . 在之前的基础上卖股票

和上面的情况特别类似，在此简单地说一下区别。

因为是卖股票， $k$ 这次要比 $j$ 大。但要小于等于 $j + bs_i$

这次交易卖了 $k - j$ 张邮票，赚得 $(k - j) \times bp_i$​ 元。

整理一下，转移方程为：

$f_{i,j}​=max(f_{i,j}\ ,,\ ,f_{i-w-1,k}+(k-j)\times bp_i)$

$(j < k \leqslant j + bs_i)$

Q：为什么可以使用单调性优化？

A：

上面的 3，4 两种情况，列起来头头是道，但我们深入计算，发现时间复杂度是三次方级的。很显然，我们要想尽办法，把时间复杂度降到二次方级。

这个时候发现那两种情况，实际上可以使用单调性优化。此时达到降时间复杂度的目标。

就以第 3 种情况，在之前的基础上买股票为例子吧。

再重复提一下那个转移方程：

$f_{i,j}=max(f_{i,j}\ ,,\ ,f_{i-w-1,k}-(j-k)\times ap_i)$

$(j - as_i \leqslant k < j)$

运用乘法分配率：

$f_{i,j}​=max(f_{i,j}\ ,,\ ,f_{i-w-1,k}-j\times ap_i+k\times ap_i)$

$(j - as_i \leqslant k < j)$

既然要将状态转移给 fi,jf_{i,j}fi,j​，此时 jjj 可以从 maxmaxmax 中提取出，此时转移方程变为：

$f_{i,j}​=max(f_{i,j}\ ,,\ ,f_{i-w-1,k}+k\times ap_i)-j\times ap_i$

$(j - as_i \leqslant k < j)$

此时，我们发现以上的转移方程符合单调性优化的条件，故可以使用单调性优化。

没有理解地，可以这么想：由于转移有这么一个区间前提：$(j - as_i \leqslant k < j)$，又因为转移方程中出现了 max，也就是说转移的目的是从该区间中，找到某个最大的值，基础好的你应该已经发现这就是滑动窗口了吧？只不过放进单调队列的元素，是 $f_{i-w-1,k}+k\times ap_i​$，但这并不影响转移。

那么第 4 种情况的转移，我就不多解释了，它的转移方程可以整理为：

$f_{i,j}​=max(f_{i,j}\ ,,\ ,f_{i-w-1,k}+k \times bp_i)-j \times bp_i$

$(j < k \leqslant j + bs_i)$

好像除了后面的转移区间要求，两个整理后的方程几乎都是一样的。

对了，还有一个细节，是第 3 种情况转移应该顺序，第 4 种情况转移应该逆序，这个不难理解，先自己想想吧。