2021牛客多校第一场I Increasing Subsequence-期望DP

[传送门][https://ac.nowcoder.com/acm/contest/11166/I]

题意:

一个长为$n$的排列,有两个人轮流从中取数,每一轮中所取的数需要满足如下规则:

  1. 取的数大于之前所有人取的数
  2. 取的数的下标大于取数人之前取的数的下标
  3. 如果有多种取数方案,则随机进行取数
  4. 第一个人第一次取数随机
  5. 如果有人没法再取数,游戏结束

求最后期望能取数多少次。

阅读更多