P2569 (SCOI2010)股票交易

P2569 (SCOI2010)股票交易

巧妙的单调性优化

设 $f(t,x)$ 表示第 $t$ 天，手持 $x$ 只股票时的最大利润，显然有几种转移方式

1. 在第 $t$ 天什么也不做

   $f(t,x)=f(t-1,x)$

2. 在第 $t$ 天买进股票，刚好买 $x$ 只

   $f(t,x)=-xAP_i$

3. 在第 $t$ 天买进股票

   $f(t,x)=\max\limits_{1\le x'\le AS_i}(f(t-w-1,x-x') - x'AP_i)$

   为什么是 $t-w-1$ 呢，假设实际上上一次操作是在第 $t'$ 天，那么就相当于从第 $t'$ 天到第 $t-w-1$ 天什么也不做，这种情况在上面已经考虑过了，所以答案 $f(t-w-1,x-x')$ 不会比 $f(t',x-x')$ 小。

4. 在第 $t$ 天卖出股票

   $f(t,x)=\max\limits_{1\le x'\le BS_i}\left(f(t-w-1,x+x')+x'BP_i\right)$

这个时候，暴力转移复杂度 $O(n^3)$ ，考虑优化。

看着这个式子不爽，搞它 ➜ $f(t,x)=\max\limits_{1\le x'\le AS_i}(f(t-w-1,x-x')-x'AP_i)$

先把 $-x'AP_i$ 拆成 $(x-x')AP_i-xAP_i$ ，方便操作（前面也有一个 $x-x'$）

$f(t,x)=\max\limits_{1\le x'\le AS_i}(f(t-w-1,x-x') + ((x-x')AP_i)-xAP_i)$

提出来

$f(t,x)=\max\limits_{1\le x'\le AS_i}(f(t-w-1,x-x') + ((x-x')AP_i))-xAPi$

发现 $f(t-w-1,x-x')+(x-x'AP_i)$ 随着 $x$ 的增长，它的范围是变化不大的，每次增加一个元素 $f(t-w-1,x)+xAP_i$，减去 $x'>AS_i$ 的元素

这样就能用单调性优化了，复杂度 $O(n^2)$

Tips: 当时做题的时候没有考虑到第二种情况实际上是不受 $w$ 的限制的，只受 $AS_i$ 的限制 卡了我一个晚上