你要抓神奇宝贝! 现在一共有 

N

 只神奇宝贝。 你有 

a

 个『宝贝球』和 

b

 个『超级球』。 『宝贝球』抓到第 

i

 只神奇宝贝的概率是 

p_i

 ,『超级球』抓到的概率则是 

u_i

 。 不能往同一只神奇宝贝上使用超过一个同种的『球』,但是可以往同一只上既使用『宝贝球』又使用『超级球』(都抓到算一个)。 请合理分配每个球抓谁,使得你抓到神奇宝贝的总个数期望最大,并输出这个值。

设dp[i][j][k] 前i个神奇宝贝 用了j个a球 k个b球 期望的最大值是多少 那么直接

dp即可 但是显然复杂度是不对的n^3 那么考虑wqs二分 发现函数单增 那么我们二分一下每次使用a,b两种球会带来的减少量 复杂度n*log*log即可解决

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论