考虑 “高兴” 的点所形成的子序列(显然这是单增的)并插入其他的点(决策集合也只会扩大)。先将原序列升序排序。
直接 DP 这个序列, (f(pos, cnt)) 为当前最大值位置 (pos),已经决策的点数 (cnt le last_i + 1),(last_i = max{j : 2a_j le a_i}),插入一个点,有两种转移:
- (f(pos, cnt) leftarrow sum_{pos' le last_i} f(pos', cnt - 1))
- (f(pos, cnt) leftarrow f(pos, cnt - 1))
考虑省去第二维,每次插入一个 ”高兴“ 的点后直接将可以插入的 ”不高兴“ 点全部插入到剩余的空位中。
则有
[f_i = sum_{j = 1}^{last_i} f_j cdot (n - last_j - 2)^{underline{last_i - last_j - 1}}
]
注意到 (j in [last_j, last_i])。
容易前缀和优化。注意特判无解(即点没有被插入完)的情况。
复杂度 (mathcal O(n log n))。