P8357 「WHOI-1」Derives

· · 题解

算是对两个长得几乎一摸一样的验题人和出题人题解的补充。

Part Ⅰ

我们一步一步来，先从朴素的动态规划来。我们记 f_i 为选 i 个硬币的方案数，此时官方题解就直接甩了一个柿子上来。

f_i=a\times i+\min\limits_{j=1}^{i-1}\{f_j+\lceil \frac{i}{j}\rceil\times b\}

我们不妨理解一下他的具体含义，转移过程其实实在枚举 m_i，显然，当我们选定一个 m_i 时，问题就缩减为一个 f_{m_i} 的子问题。那么显然加上这次操作的代价就有了最后的答案。

Part Ⅱ

我们注意到 \lceil \frac{i}{j}\rceil = \lfloor \frac{i-1}{j}\rfloor + 1，根据我们学过的数论分块知识，直接对 \lfloor \frac{i-1}{j}\rfloor 数论分块就好了，可以观察到 \forall i>j,f_i\geq f_j，又因为显然数论分块值是连续的，所以每次转移必然转移左端点。

Part Ⅲ

如何构造映射？我们观察到每个需要用到的转移点必然是数论分块的端点，显然这个端点和数论分块的分母无关，因此可以构造类似的映射。