Codeforces #739E Gosha is hunting

题目链接

题解链接

题目大意:戈沙要捕捉口袋妖怪,他有两种精灵球。第一种有个,第二种有个。每个口袋妖怪只能被捕捉一次。

一共有个口袋妖怪,用一种球捕捉第个成功的概率为,用第二种球捕捉第个成功的概率为,用两种同时捕捉第个成功的概率为

问捕捉的口袋妖怪的个数期望值最大是多少?

 

Solution

这道题网上很多博客的题解都是的。

实际上可以做到,CF上有一篇博客讲了这个方法。

 

首先我们可以得到一个很显然的 DP。

表示当前考虑到第个口袋妖怪,用了个第一种球,用了个第二种球的期望。

枚举选哪个或两个都选直接转移。

我们观察到对于这一维,不难想象当增大时,增加的贡献越来越少,所以我们可以对于这一维二分斜率来做。

对于这一维,也是一样的,在二分里再套一层二分斜率。

复杂度

 

Hints

二分斜率是对坐标即每次操作而言,与操作的具体贡献形式无关。

 

Code