标签：num dfrac align NOI2007 jRate 兑换 货币 max gets

前言

想起之前一道叫股票的题, 也是这么长的题面, 不过事已至此, 先读题吧

最近这么菜一定要记住每日一练和 \(\rm{whk}\) 啊

思路

首先直觉是比例不好处理, 肯定是要转化的

发现最后写了一句

必然存在一种最优的买卖方案满足:
每次买进操作使用完所有的人民币, 每次卖出操作卖出所有的金券

---

有这个性质明显更好做, 每次可以钦定 \(OP = 100\) , 但是为什么呢, 考虑证明
你发现每次买入相当于对 \(num_A, num_B\) 的比例进行调整, 每次卖出相当于按照这个比例和 \(A_k, B_k\) 的比例赚钱
形式化的来讲, 买入相当于

\[rate = \frac{num_A}{num_B} \to \frac{num_A + \frac{Rate_k IP}{Rate_kA_k + B_k}}{num_B + \frac{IP}{Rate_kA_k + B_k}} \\ \ \\ num_B \gets num_B + \frac{IP}{Rate_kA_k + B_k} \]

卖出相当于

\[\begin{align*} profit & = (num_A A_k + num_B B_k) \times OP\% \\ & = num_B (A_K rate + B_k) \times OP \% \end{align*} \]

一次能赚钱, 显然是要把 \(A_k, B_k\) 全部甩出去赚的最多, 买入同理

你可以当我没有证明, 我自己也看不懂

---

考虑现在怎么做
你发现, 如果把 \(N\) 天分成 \(k\) 段由买入和卖出组成的时间区间 \([l, r]\) , (注意 \(l = r\) 是非法的; 同天内只考虑先卖再买, 不然没有意义) , 我们可以考虑 \(\rm{dp}\)

令 \(f_i\) 表示对于以 \(i\) 结尾的分段, 最优的利润 (也就是手上还有多少钱)
也就是说买 \(A, B\) 的数量为

\[x_i=\dfrac{f_iRate_i}{A_iRate_i+B_i} \\ \ \\ y_i=\dfrac{f_i}{A_iRate_i+B_i} \]

容易写出柿子

\[\begin{align*} f_i \gets \begin{cases} f_{i-1} \\ \max\limits_{j \in [0, i)} A_ix_j+B_iy_j \end{cases} \end{align*} \]

考虑第二个柿子怎么处理
你发现这种跟 \(i, j\) 都有关的东西, 拆一下转化成斜率优化的形式即可

---

首先化成同项, 否则就会像下面一样

\[\begin{align*} f_i \gets \begin{cases} f_{i-1} \\ \max\limits_{j \in [0, i)} \dfrac{(A_iRate_j + B_i)f_j}{A_jRate_j+B_j} \\ \end{cases} \\ \end{align*} \\ \Downarrow \\ f_i = \max\limits_{j \in [0, i)} \dfrac{(A_iRate_j + B_i)f_j}{A_jRate_j+B_j} \\ \begin{align*} f_i & = \dfrac{(A_iRate_j + B_i)f_j}{A_jRate_j+B_j} \\ f_i & = \dfrac{(A_iRate_j + B_i)f_j}{A_jRate_j+B_j} \\ \end{align*} \]

根本不对

也不能找 \(x_j, y_j\) 的关系

\[f_i \gets \max\limits_{j \in [0, i)} A_ix_j+B_iy_j \\ f_i \gets \max\limits_{j \in [0, i)} A_i y_j Rate_j + B_i y_j \\ f_i \gets \max\limits_{j \in [0, i)} y_j (A_i Rate_j + B_i) \\ \]

---

考虑

\[f_i \gets \max\limits_{j \in [0, i)} A_ix_j+B_iy_j \\ f_i \gets \max\limits_{j \in [0, i)} B_i (\frac{A_i}{B_i} x_j + y_j) \\ f_i \gets B_i\max\limits_{j \in [0, i)} (\frac{A_i}{B_i} x_j + y_j) \\ \]

继续转化, 记 \(\frac{A_i}{B_i} = v_i\)

\[\begin{align*} f_i & = (v_i x_j + y_j) \\ f_i & = v_i\dfrac{f_jRate_j}{A_jRate_j+B_j} + \dfrac{f_j}{A_jRate_j+B_j} \\ \end{align*}\]

可以令 \(x = v_i, y = f_i, k = \dfrac{f_jRate_j}{A_jRate_j+B_j} , b = \dfrac{f_j}{A_jRate_j+B_j}\) 李超线段树维护

发现 \(x\) 可能为小数, 怎么办
我们考虑把 \(x\) 离散化对应到整数上即可, 不影响答案

注意去重函数的精度问题

实现

这种经典题要写代码, 第一道李超线段树

总结

斜率优化类问题常见的区间划分, 一般来说, 买卖问题这种两点型问题, 时间区间划分很常见

注意讨论啥也不干的情况
注意斜率优化把 \(i, j\) 都有的柿子化成同项之后再处理, 一般的方法是提出一个只与 \(i\) 相关的因式
这题也是巧妙地转化, 人类智慧美丽时刻

遇到小数可以考虑离散化

标签：num,dfrac,align,NOI2007,jRate,兑换,货币,max,gets
From： https://www.cnblogs.com/YzaCsp/p/18673459