【题解】CF303E 概率 dp优化

· · 题解

随机值第 k 大，求排名，这种不太好记录之前的值的信息，不好考虑完整的大小关系的随机问题一种套路做法是考虑枚举一个值，作为最终取的值或是前几大的分界线考虑，再来统计其他值和这个值的相对大小关系。

问题是在实数域上的，所以两个变量相同的概率是 0。将问题离散化，求出若干值域区间 [c_i,c_{i+1})，满足区间内值可以被选取变量集合是相同的。

考虑枚举一个值域 [c_k,c_{k+1})，并钦定某个值在里面。然后来统计答案：

$$ f'_{i,j}=f_{i,j}\times p(a \geq c_{k+1})+ f_{i,j-1}\times p(c_k\leq a < c_{k+1})+f_{i-1,j}\times p(a<c_k) $$ 统计答案时枚举 $i,j$，对于这组 $i,j$，可能的排名为 $[i+1,i+j+1]$，这些排名一定是等概率的，因为区间 $[c_k,c_{k+1})$ 内的这些值是全是随机的，$i$ 在每个排名的概率是相同的。 进行一次 dp 的复杂度为 $O(n^3)$，枚举一个值域区间，枚举一个位置，复杂度 $O(n^5)$，可以通过。 优化在[这里](https://www.cnblogs.com/Dreamerkk/p/17703589.html)，可以做到 $O(n^4)$。