source:zr 二十联测 day16 B
题意
给定 \(n\) 个数 \(a_i\)。
每次你需要花费 \(c\) 在剩余的数中均匀随机获得一个数,你可以选择留下这个数,此时游戏结束且得分为该数值;否则将这个数扔掉(但不放回),然后游戏继续。
求最大期望。要求时间复杂度 \(O(n)\)。
分析
将 \(a_i\) 降序排序。
首先需要发现,我们的最优策略一定形如 \(t_1,t_2,\cdots,t_k\),表示我在第 \(i\) 次游戏时抽到了下标 \(\le t_i\) 的数就见好就收,否则把数扔掉。其次一定有 \(t_i\) 单调不升。
考虑设计一个暴力 DP。设 \(f_{i,j}\) 表示剩下 \(i\) 个数,当前极长的没被删的前缀长度为 \(j\) 的最大期望。由于 \(t_i\) 单调不升,所以在 \(i-1\) 决策完之后,\(>t_{i-1}\) 的那些数如果抽到是肯定要丢的。转移考虑抽到的是肯定要丢的还是可以决策留不留的,转移方程:\(f_{i,j}=\frac{i-j}{i}f_{i-1,j}+\frac{\sum_{k=1}^j\max(a_k,f_{i-1,k-1})}{i}-c\)。
裸实现时间复杂度 \(O(n^3)\)。由于状态数已经达到了平方级别,所以考虑怎么压状态。
考虑到对于那些一定要丢的数,我们并不关心具体选了哪个,所以我们不妨这么考虑:如果删了一定要丢的数,钦定它选了最小的那个数,据此设计 DP 状态为 \(f_i\) 表示剩了 \(i\) 张牌的最大期望。转移考虑枚举 \(t_i=p\):\(f_{i}=\frac{i-p}{i}f_{i-1}+\frac{\sum_{i=1}^p s_i}{i}\)。复杂度平方。
考虑优化。发现 \(p\) 指针右移造成的增量为 \(f_{i-1}-a_p\),由于 \(a_p\) 单调,所以我们实际上只需要找到第一个 \(\ge f_{i-1}\) 的 \(a_p\) 即可。若采用二分复杂度带老哥,但是发现 \(f_i\) 本身也是单调的,据此可以双指针,复杂度线性。
标签:frac,抽到,复杂度,WI,单调,考虑,ZR From: https://www.cnblogs.com/dcytrl/p/18535463