CF1601D Difficult Mountain 题解

万弘

2021-10-28 22:13:20

Solution

提供一个场上写的,有点奇怪的做法。 首先题目要求有序的选取一些尽量大的元素。 那么按照套路,我们可以按某种规则排序,然后考虑dp。 那么问题变成 - 怎么排序,使得存在最优解是排序后序列的一个子序列(即让dp无后效性) - 已知顺序,怎么dp。 其中dp部分其实是很简单的。 令 $ f(i,j) $ 为考虑前 $ i $ 个人,山高度为 $ j, $ 最多有多少个人爬过山。 考虑加入一个 $ (s,a) $ ,用线段树优化即可, $ O(n\log n) $ ,因为不是精妙之处就不细讲了。 然后考虑排序。对于 $ (s_i,a_i) $ 和 $ (s_j,a_j) $ ,若 $ a_i\le s_j,a_j\le s_i $ 那么两者顺序无所谓,否则若 $ a_i\le s_j $ ,那么 $ i $ 应该在 $ j $ 前。 但容易发现这样没有传递性,无法排序。 然后我手搓出来了一个方案:若 $ \frac{a_i}{s_j}<\frac{a_j}{s_i} $ ,那么令 $ i $ 在 $ j $ 前。 传递性:其实就是按 $ a_i\times s_i $ 排序。然后若 $ a_i\le s_j $ 而 $ a_j> s_i $ 那么也一定有 $ i $ 在 $ j $ 前。 总复杂度 $ O(n\log n) $ .