P2569 (SCOI2010)股票交易
巧妙的单调性优化
设 f(t,x) 表示第 t 天,手持 x 只股票时的最大利润,显然有几种转移方式
-
在第 t 天什么也不做
f(t,x)=f(t−1,x)
-
在第 t 天买进股票,刚好买 x 只
f(t,x)=−xAPi
-
在第 t 天买进股票
f(t,x)=1≤x′≤ASimax(f(t−w−1,x−x′)−x′APi)
为什么是 t−w−1 呢,假设实际上上一次操作是在第 t′ 天,那么就相当于从第 t′ 天到第 t−w−1 天什么也不做,这种情况在上面已经考虑过了,所以答案 f(t−w−1,x−x′) 不会比 f(t′,x−x′) 小。
-
在第 t 天卖出股票
f(t,x)=1≤x′≤BSimax(f(t−w−1,x+x′)+x′BPi)
这个时候,暴力转移复杂度 O(n3) ,考虑优化。
看着这个式子不爽,搞它 ➜ f(t,x)=1≤x′≤ASimax(f(t−w−1,x−x′)−x′APi)
先把 −x′APi 拆成 (x−x′)APi−xAPi ,方便操作(前面也有一个 x−x′)
f(t,x)=1≤x′≤ASimax(f(t−w−1,x−x′)+((x−x′)APi)−xAPi)
提出来
f(t,x)=1≤x′≤ASimax(f(t−w−1,x−x′)+((x−x′)APi))−xAPi
发现 f(t−w−1,x−x′)+(x−x′APi) 随着 x 的增长,它的范围是变化不大的,每次增加一个元素 f(t−w−1,x)+xAPi,减去 x′>ASi 的元素
这样就能用单调性优化了,复杂度 O(n2)
Tips: 当时做题的时候没有考虑到第二种情况实际上是不受 w 的限制的,只受 ASi 的限制 卡了我一个晚上