2023-09-18
题目
难度&重要性(1~10):8
题目来源
luogu
题目算法
dp,组合数学
解题思路
这道题第一眼就是啥也不管，先排序。然后考虑如何 dp。
先讲一讲我第一眼的 \(O(n^3)\) 思路吧：
首先，我将状态设计 \(f_{i,j}\) 其中 \(i\) 表示枚举到第 \(i\) 个位置，\(j\) 表示排完序后最大值为 \(j\) 的方案数。
转移我就不细讲了，然后我发现我的状态设计的简直像一个小可爱一样。
因为我们是已经将数组排序的，那么我们当前既然枚举到了第 \(i\) 个位置，最大值就可以直接定为是 \(a_i\) 的。
然后我们只需要预处理一下小于等于 \(\dfrac{1}{2}a_i\) 的个数记为 \(x_i\)。
这样我们就可以轻松得到转移方程式：
\[f_i=\sum\limits_{j=0}^{x_i}f_j\times A_{n-x_j-2}^{x_i-x_j-1}
\]
然后这道题就做完了，时间复杂度 \(O{n^2}\)。
完成状态
已完成