codeforces 739E Gosha is hunting

codeforces 739E Gosha is hunting

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

N

N 只神奇宝贝。 你有

a

a 个『宝贝球』和

b

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

i

i 只神奇宝贝的概率是

p_i

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

u_i

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

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

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

#include#define eps 1e-8using namespace std;const int N=2200;int n,numa[N],numb[N],A,B;double a[N],b[N],dp[N];inline void gao(double ca,double cb){ for (int i=1;i<=n;++i){ dp[i]=dp[i-1];numa[i]=numa[i-1];numb[i]=numb[i-1]; if(dp[i-1]+a[i]-ca>dp[i]){ dp[i]=dp[i-1]+a[i]-ca;numa[i]=numa[i-1]+1;numb[i]=numb[i-1]; } if (dp[i-1]+b[i]-cb>dp[i]){ dp[i]=dp[i-1]+b[i]-cb;numa[i]=numa[i-1];numb[i]=numb[i-1]+1; } if (dp[i-1]+a[i]+b[i]-a[i]*b[i]-ca-cb>dp[i]){ dp[i]=dp[i-1]+a[i]+b[i]-a[i]*b[i]-ca-cb;numa[i]=numa[i-1]+1;numb[i]=numb[i-1]+1; } }}int main(){ freopen("cf.in","r",stdin); scanf("%d%d%d",&n,&A,&B); for (int i=1;i<=n;++i) scanf("%lf",&a[i]); for (int i=1;i<=n;++i) scanf("%lf",&b[i]); double l1=0,r1=1,l2,r2; while(l1

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。