标签：kA frac align num NOI2007 Rate 兑换 货币 考虑

前言

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

最近这么菜一定要记住每日一练和 \(\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=\max(f_i,f_{i-1}) \\ f_i=\max a_ix_j+b_iy_j \end{cases} \end{align*} \]

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

注意 \(x\) 可能是小数, 考虑离散化

总结

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

遇到小数可以考虑离散化

标签：kA,frac,align,num,NOI2007,Rate,兑换,货币,考虑
From： https://www.cnblogs.com/YzaCsp/p/18673006