题解：P14805 [CCPC 2024 哈尔滨站] 弹珠赛跑

· · 题解

联考搬了这个题，场了。

我们发现中位数这个东西不好在 DP 的时候计入状态，考虑枚举中位数 x，然后在 DP 的时候计算以 x 为中位数的概率。

可以设 dp_{i,j} 为到第 i 个点，比中位数大的点为 j 的概率。得到一个朴素的 O(n^2m^2) 做法。

发现其实如果你把这个 x 数组排序一遍就会发现，对于相邻的两个值 x_i,x_{i+1} 来说，他们之间的 dp 数组的改变量只有加入了得到 x_i 答案的点，然后删除了得到 x_{i+1} 答案的点，这样我们就可以做一遍回退背包，做到 O(n) 的转移。

总时间复杂度 O(m^2n)，注意如果答案有相同的情况出现，可以将靠前的数视为较小。

Code