「单调优化 dp」做题记录

1. P1941 [NOIP2014 提高组] 飞扬的小鸟

   设 \(f(i, j)\) 表示使小鸟到达 \((i, j)\) 所需的最少点击数。

   不难写出转移方程：

   \[f(i, j) = \min \begin{cases} f(i-1, j + y_{i-1}), \text{if} j + y_{i-1} \le m \\ f(i-1, x - kx_{i-1}), k \in \mathbb{N}^+ \and j - kx_{i-1} \ge 1 \end{cases} \]

   其中第一种情况对应在上一点不点击，第二种情况对应在上一点点击若干次（\(k\) 次）。由于小鸟高度为 \(m\) 时，无法再上升，所以 \(j = m\) 的情况要特殊处理。

   初始化：

   \[f(i, j) = \begin{cases} 0, i = 0 \\ +\infty, \text{Otherwise} \end{cases} \]

   如果 \(\forall 1 \le j \le m\)，\(f(n, m) = +\infty\)，则无法到达终点，否则到达终点的最小点击数为 \(\min_{1 \le j \le m} f(n, j)\)。

   容易发现，由于要枚举 \(k\)，每次转移的时间复杂度大于 \(O(1)\)。虽然在开启 O2 的情况下能通过此题，但我们仍需更好的转移方程。

   但是我还没搞懂优化，洛谷题解写的都是什么东西？还有这不是单调优化题单里的题吗，我怎么没看出单调优化，题解里都在说完全背包的事

   标签：方程,le,int,max,sum,dp,优化,单调
   From： https://www.cnblogs.com/dengstar/p/18330906