CF739E Gosha is hunting

发表于 | 分类于

Description

有\(n\)个精灵，你手里有\(A\)个普通球和\(B\)个超级球。对于第\(i\)个精灵，只用普通球捕获的概率为\(p_i\)，只用超级球捕获的概率为\(u_i\)。对于每只精灵，你可以不去捕获他，也可以选择用普通球和超级球中的一种去捕获，也可以先用一种再用另一种，但是要注意不能在同一个精灵上使用多个普通球或者多个超级球。

请你安排一种合理的策略，使得捕获精灵的期望尽可能大，并输出最大期望。

\(2\leq n\leq 2000,0\leq A, B\leq n, 0\leq p_i,u_i\leq 1\)。

Solution

wqs二分第二题……

看到个数限制，每个有收益，要素察觉（意味深）

然后考虑往wqs二分上靠，但是限制有两种，那么我们就要考虑用wqs二分套wqs二分了。

然后下面考虑那玩意是不是真的有凸性……这个东西是三维的情况，普通球限制（设为\(x\)）、超级球限制（设为\(y\)）和收益（设为\(z\)）这三维，那么我们要求\(x\)固定的时候\(y\)是凸的，并且每种\(x\)的最优解也是凸的。

固定\(x\)的话，我们考虑\(y\)不断增大的情况。在\(x\)固定且限制存在的情况下，我们会发现每个超级球能给答案带来的最大贡献是一定的，那么考虑将这些贡献排序，我们一定会取前\(y\)项的和。也就是说超级球给答案的贡献是一个前缀和，差分一下就会得到原序列，而原序列是一个递减的序列，所以斜率递减，自然就凸力，，，

那么\(x\)的最优解是凸的，证明也是前缀和这一套理论……\(x\)限制存在时一定会优先选贡献最大的，然后排序之后就相当于前缀和，前缀和差分完了是递减的所以凸。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
const int maxn = 100005;
using R = double;
const R eps = 1e-9;
R f[maxn], p[maxn], u[maxn];
int cnt_a[maxn], cnt_b[maxn];
int n;
bool dp(R v1, R v2) {
  f[0] = 0; cnt_a[0] = cnt_b[0] = 0;
  for(int i = 1; i <= n; i ++) {
    f[i] = f[i - 1]; cnt_a[i] = cnt_a[i - 1];
    cnt_b[i] = cnt_b[i - 1];
    if(f[i - 1] + p[i] - v1 > f[i]) {
      f[i] = f[i - 1] + p[i] - v1;
      cnt_a[i] = cnt_a[i - 1] + 1;
      cnt_b[i] = cnt_b[i - 1];
    }
    if(f[i - 1] + u[i] - v2 > f[i]) {
      f[i] = f[i - 1] + u[i] - v2;
      cnt_a[i] = cnt_a[i - 1];
      cnt_b[i] = cnt_b[i - 1] + 1;
    }
    if(f[i - 1] + 1 - (1 - p[i]) * (1 - u[i]) - v1 - v2 > f[i]) {
      f[i] = f[i - 1] + 1 - (1 - p[i]) * (1 - u[i]) - v1 - v2;
      cnt_a[i] = cnt_a[i - 1] + 1;
      cnt_b[i] = cnt_b[i - 1] + 1;
    }
  }
  return true;
}

int main() {
  int A, B; scanf("%d%d%d", &n, &A, &B);
  for(int i = 1; i <= n; i ++) scanf("%lf", &p[i]);
  for(int i = 1; i <= n; i ++) scanf("%lf", &u[i]);
  R l1 = 0, r1 = 1, l2, r2;
  while(r1 - l1 > eps) {
    R m1 = (l1 + r1) / 2;
    l2 = 0, r2 = 1;
    while(r2 - l2 > eps) {
      R m2 = (l2 + r2) / 2;
      if(dp(m1, m2) && cnt_b[n] > B) {
        l2 = m2;
      } else {
        r2 = m2;
      }
    }
    if(dp(m1, r2) && cnt_a[n] > A) {
      l1 = m1;
    } else {
      r1 = m1;
    }
  }
  dp(r1, r2);
  printf("%.5lf\n", f[n] + (R)A * r1 + (R)B * r2);
  return 0;
}