题目

方法学习于 maspy 的博客。

一个很简单的想法是，可以使用背包。

使得 $dp_{a, b}$ 表示用了 $a$ 个 I 类球和 $b$ 个 II 类球。

但是直接转移的话是 $O(NAB)$ 的，无法接受。

这位日本哥采用的办法是，将 $N$ 个神奇宝贝随机，然后用 I 类球的期望个数是 $\frac{i}{N} \times A$，然后在这附近找 $K$ 个就可以了。

复杂度就是 $O(NK^2)$，错误率分析在他的博客。

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
void solve() {

  int n, a, b;
  read(n, a, b);
  vc<double> p(n), q(n);
  read(p, q);
  vi per(n);
  iota(all(per), 0);
  shuffle(all(per), rng);

  vc<double> P(n), Q(n);
  rep(i, n) {
    P[i] = p[per[i]];
    Q[i] = q[per[i]];
  }
  p.swap(P);
  q.swap(Q);

  vc<vc<double>> dp(a + 1, vc<double>(b + 1, 0.00));
  rep (i, n) {
    double pp = p[i];
    double qq = q[i];
    double pq = pp + qq - pp * qq;
    int na = a * i / n;
    int nb = b * i / n;
    int la = na - 50;
    int ra = na + 50;
    int lb = nb - 50;
    int rb = nb + 50;
    cmax(la, 0);
    cmax(lb, 0);
    cmin(ra, i + 1);
    cmin(rb, i + 1);
    for (int x = ra - 1; x >= la; x--) {
      for (int y = rb - 1; y >= lb; y--) {
        if (x + 1 <= a && y + 0 <= b)
          cmax(dp[x + 1][y + 0], dp[x][y] + pp);
        if (x + 0 <= a && y + 1 <= b)
          cmax(dp[x + 0][y + 1], dp[x][y] + qq);
        if (x + 1 <= a && y + 1 <= b)
          cmax(dp[x + 1][y + 1], dp[x][y] + pq);
      }
    }
  }

  cout << dp[a][b] << "\n"; 
}