题解：AT_abc470_e [ABC470E] Concentration

· · 题解

概率模板题，但是感觉概率属于不怎么熟的一块。

首先考虑一下最优策略：在不知道的牌里随便开一张，如果这张之前见过，那么直接配对。如果没见过，再随便开一张。

这个过程其实可以看作在集合内的操作，数的顺序是无关紧要的。所以这其实等价于 a_i \leftarrow \overline{a}。这样所有元素的值就一样了，不需要状压了。

::::info[简要证明]

后来简单想了一下。

对于任意一个末尾状态（就是 i = 0 或者 j = n），所有 n 中选择 j 对情况得分权重其实是一样的。所以平均是正确的。

说的有点抽象了。

::::

设计 DP 状态 f(i,j,k) 代表剩余 i 条命，已经配对 j 对，已经知道但没配对 k 张的期望得分。我们只需要按照最优策略暴力转移即可。

细节：概率题一般记忆化搜索更好写，记得死亡要在得分前判定。

BTW，这场 C 评绿我还是很惊讶的。