题解 CF739E 【Gosha is hunting】

81179332_ · 2020-07-07 15:09:52 · 题解

我们每多选一个球所增加的期望一定是不断减少的，否则我们上一步可以选这个球使得上一步的答案更大

所以是个凸包

所以是个 wqs 二分

由于有 a,b 两个限制，所以我们 wqs 二分套 wqs 二分

看上去很毒瘤，实则很好写

const int N = 2010;
double u[N],v[N],q[N];
int n,a,b;
struct DP
{
    double val;int a,b;
    friend bool operator < (DP u,DP v) { return u.val < v.val; }
    friend DP operator + (DP u,DP v) { return {u.val + v.val,u.a + v.a,u.b + v.b}; }
}dp[N];
void check2(double x,double y)
{
    dp[0] = {0,0,0};
    for(int i = 1;i <= n;i++)
        dp[i] = max(max(max(dp[i - 1],dp[i - 1] + (DP){q[i] - x - y,1,1}),dp[i - 1] + (DP){u[i] - x,1,0}),dp[i - 1] + (DP){v[i] - y,0,1});
}
double l2;
void check1(double x)
{
    double l = 0,r = 1;int T = 40;
    while(T--)
    {
        double mid = (l + r) / 2;
        check2(x,mid);
        if(dp[n].b >= b) l = mid;
        else r = mid;
    }
    check2(x,l),l2 = l;
}
int main()
{
    n = read(),a = read(),b = read();
    for(int i = 1;i <= n;i++) scanf("%lf",u + i);
    for(int i = 1;i <= n;i++) scanf("%lf",v + i);
    for(int i = 1;i <= n;i++) q[i] = u[i] + v[i] - u[i] * v[i];
    double l = 0,r = 1;int T = 40;
    while(T--)
    {
        double mid = (l + r) / 2;
        check1(mid);
        if(dp[n].a >= a) l = mid;
        else r = mid;
    }check1(l);
    printf("%.5lf\n",dp[n].val + l * a + l2 * b);
}