【CF739E】Gosha is hunting（WQS二分套WQS二分）

点此看题面

大致题意： 你有两种捕捉球（分别为$A$个和$B$个），要捕捉$n$个神奇宝贝，第$i$个神奇宝贝被第一种球捕捉的概率是$s{1}_i$，被第二种球捕捉的概率是$s{2}_i$，问在最优策略下期望捕捉到的神奇宝贝数量。

---

$WQS$二分

这应该是一道比较经典的$WQS$二分题（毕竟是 $WQS$二分套$WQS$二分）。

$Link$

$WQS$二分 详见博客 WQS二分学习笔记

---

$WQS$二分套$WQS$二分

如果你知道$WQS$二分，应该就不难想到$WQS$二分一个代价$C1$，表示每使用一个第一种球所需要的代价，然后再$WQS$二分一个代价$C2$，表示每使用一个第二种球所需要的代价。于是就成了$WQS$二分套$WQS$二分。

---

$DP$转移

在$WQS$二分后，就是$DP$了。

我们可以用$f_i$表示到第$i$个神奇宝贝为止捕捉到的神奇宝贝总数的最大期望值，并用$g{1}_i$表示此时使用的第一种捕捉球个数，用$g{2}_i$表示此时使用的第二种捕捉球个数。

其实$DP$也是挺简单的，共有$4$种情况：

不使用捕捉球。$f_i=f_{i-1},g{1}_i=g{1}_{i-1},g{2}_i=g{2}_{i-1}$。使用第一种捕捉球。$f_i=f_{i-1}+s{1}_i-C1,g{1}_i=g{1}_{i-1}+1,g{2}_i=g{2}_{i-1}$使用第二种捕捉球。$f_i=f_{i-1}+s{2}_i-C2,g{1}_i=g{1}_{i-1},g{2}_i=g{2}_{i-1}+1$同时使用两种捕捉球。$f_i=f_{i-1}+s{1}_i+s{2}_i-C1-C2-s{1}_i\ast s{2}_i,g{1}_i=g{1}_{i-1}+1,g{2}_i=g{2}_{i-1}+1$

这样就可以了。

---

代码

#include<bits/stdc++.h> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)<(y)?(x):(y)) #define uint unsigned int #define LL long long #define ull unsigned long long #define swap(x,y) (x^=y,y^=x,x^=y) #define abs(x) ((x)<0?-(x):(x)) #define INF 1e9 #define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD)) #define ten(x) (((x)<<3)+((x)<<1)) #define N 100000 #define eps 1e-12 using namespace std; int n,A,B;double s1[N+5],s2[N+5]; class Class_WQS//WQS二分套WQS二分 { private: double C1,C2,f[N+5];int g1[N+5],g2[N+5];//用f[i]表示到第i个神奇宝贝为止捕捉到的神奇宝贝总数的最大期望值，并用g1[i]表示此时使用的第一种捕捉球个数，用g2[i]表示此时使用的第二种捕捉球个数 inline void check()//DP转移 { for(register int i=1;i<=n;++i) { f[i]=f[i-1],g1[i]=g1[i-1],g2[i]=g2[i-1];//不使用捕捉球 if(f[i-1]+(s1[i]-C1)-f[i]>eps) f[i]=f[i-1]+(s1[i]-C1),g1[i]=g1[i-1]+1,g2[i]=g2[i-1];//使用第一种捕捉球 if(f[i-1]+(s2[i]-C2)-f[i]>eps) f[i]=f[i-1]+(s2[i]-C2),g1[i]=g1[i-1],g2[i]=g2[i-1]+1;//使用第二种捕捉球 if(f[i-1]+(s1[i]+s2[i]-C1-C2-s1[i]*s2[i])-f[i]>eps) f[i]=f[i-1]+(s1[i]+s2[i]-C1-C2-s1[i]*s2[i]),g1[i]=g1[i-1]+1,g2[i]=g2[i-1]+1;//同时使用两种捕捉球 } } inline void GetRes()//第二层二分，二分C2 { register double l=0.0,r=1.0; for(C2=(l+r)/2;r-l>eps;C2=(l+r)/2) { if(check(),!(g2[n]^B)) return;//找到符合条件的C2，就可以return了 g2[n]>B?l=C2:r=C2;//如果选得物品数量偏多，将l更新为C2，否则将r更新为C2 } } public: inline double GetAns()//第一层二分，二分C1 { register double l=0.0,r=1.0; for(C1=(l+r)/2;r-l>eps;C1=(l+r)/2) { if(GetRes(),!(g1[n]^A)) break;//找到符合条件的C1，就可以break了 g1[n]>A?l=C1:r=C1;//如果选得物品数量偏多，将l更新为C1，否则将r更新为C1 } return f[n]+A*C1+B*C2;//返回答案 } }WQS; int main() { register int i; scanf("%d%d%d",&n,&A,&B); for(i=1;i<=n;++i) scanf("%lf",&s1[i]); for(i=1;i<=n;++i) scanf("%lf",&s2[i]); return printf("%.10lf\n",WQS.GetAns()),0; }