LibreOJ 2112 「HNOI2015」亚瑟王

发表于 | 分类于

Description

给你\(n\)张用\(1\ldots n\)编号的牌，第\(i\)张牌发动概率为\(p_i\)，造成伤害为\(d_i\)。

然后有\(r\)回合，每回合会从当前没用过的牌里从小到大考虑，依次试图去发动（如果有一个成功发动的话就不会往下接着尝试，这回合结束）。求期望造成的伤害。

每个点共\(T(1\leq T\leq 444)\)组数据，\(1\leq n\leq 220, 0\leq r\leq 132, 0<p_i<1, 0\leq d_i\leq 1000\)。

Solution

这DP有毒.jpg

直接做是肯定不可做的……因此我们考虑利用期望线性性，分别考虑每张牌可能对答案有什么贡献。

然后还是一脸不可做……但是注意到对于每张牌，我们计算他的贡献的时候并不关心之前具体有哪些牌发动了，我们只关心他自己被考虑了多少次……（这里假设一张牌即使被用了还是会被考虑只不过不会再发动，下同）

然后考虑定义状态\(f_{i, j}\)表示第\(i\)张牌被恰好考虑了\(j\)次的概率。这样DP的话只需要考虑上一张牌发动与否即可，所以有： \[ f_{i, j} = f_{i - 1, j}(1-p_{i - 1})^j + f_{i - 1, j + 1}(1 - (1 - p_{i - 1})^{j + 1}) \] 状态转移方程还是很好懂的……前面一项就是前一张牌一直没有被发动，第二项就是前面一项曾经被发动过。

然后就没有然后了……顺便注意预处理\((1 - p_i)\)的幂能快不少。

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
#include <cstdio>
#include <cmath>
#include <algorithm>
typedef double R;
const int maxn = 225;
R p[maxn], d[maxn], f[maxn][maxn], G[maxn][maxn];
int main() {
  int T; scanf("%d", &T);
  while(T --) {
    int n, r; scanf("%d%d", &n, &r);
    for(int i = 1; i <= n; i ++) {
      scanf("%lf%lf", &p[i], &d[i]);
    }
    std::fill(f[0], f[0] + r + 2, 0.00);
    f[0][r] = 1;
    for(int i = 0; i <= n; i ++) {
      R bs = 1 - p[i]; G[i][0] = 1;
      for(int j = 1; j <= r + 1; j ++) {
        G[i][j] = G[i][j - 1] * bs;
      }
    }
    for(int i = 1; i <= n; i ++) {
      f[i][r + 1] = 0;
      for(int j = 1; j <= r; j ++) {
        f[i][j] = 0;
        f[i][j] += f[i - 1][j] * G[i - 1][j];
        f[i][j] += f[i - 1][j + 1] * (1 - G[i - 1][j + 1]);
      }
    }
    R ans = 0;
    for(int i = 1; i <= n; i ++) {
      for(int j = 1; j <= r; j ++) {
        ans += f[i][j] * (1 - G[i][j]) * d[i];
      }
    }
    printf("%.10lf\n", ans);
  }
  return 0;
}