M_sea的博客

M_sea的博客

A Mengbier

题解 CF1156F 【Card Bag】

posted on 2019-05-05 14:44:12 | under 题解 |

DP。

如果赢的话,那么拿出来的牌形成一个单调递增的序列,最后一个数重复两次。

设 $f[i][j]$ 表示抽了 $i$ 张卡(没有重复),最后抽到的是 $j$ 的获胜概率。

直接转移是 $O(n^3)$ 的,前缀和优化一下就能做到 $O(n^2)$ 了。

代码