BZOJ4008 「HNOI2015」亚瑟王

题解
动态规划, 概率期望

Description

有 $n$ 张卡牌，$r$ 局游戏，每张卡牌有 $p_i$ 的概率发动技能，如果发动会造成 $d_i​$ 的伤害。每局游戏从第一张卡牌开始开始一个个遍历，如果发动过技能则忽略继续；否则如果这张卡牌现在发动了，则结束回合；没有发动则继续。求造成的总伤害的期望。

Solution

可以想象成把 $r$ 个机会分配给每一张卡牌。$dp[i][j]$ 表示前 $i$ 张还剩 $j$ 个机会的答案

前半部分可以理解成在 $j$ 轮没有一次触发，后半部分就是至少一次触发。并且后半部分因为出触发了所以对答案有贡献，所以在 dp 的时候顺便把 ans 加上后半部分 * $d_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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Author: AcFunction
 * Date:   2019-03-17 15:45:54
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>
#define ll long long
#define db double
#define PII pair <int, int> 
#define pb push_back 
#define Fi first
#define Se second 
#define MP make_pair
#define RG register 
#define rep(i, l, r) for(RG int i = l; i <= r; i++) 
#define per(i, r, l) for(RG int i = r; i >= l; i--)

using namespace std;

void INIT() {
  ios :: sync_with_stdio(false); cin.tie(0); 
}

const int N = 250; 

int T, n, r, d[N]; 
db f[N][N], p[N]; 

db fpw(db x, int k) {
  db ret = 1.0;
  while(k) {
    if(k & 1) ret = ret * x;
    x = x * x; k >>= 1; 
  } return ret; 
}

int main() {
  INIT(); 
  cin >> T; 
  while(T--) {
    cin >> n >> r; 
    memset(f, 0, sizeof(f)); 
    rep(i, 1, n) cin >> p[i] >> d[i]; 
    f[0][r] = 1; db ans = 0; 
    rep(i, 1, n) 
      per(j, r, 0) 
        f[i][j] = f[i - 1][j] * fpw(1 - p[i], j) + f[i - 1][j + 1] * (1 - fpw(1 - p[i], j + 1)), 
        ans += d[i] * f[i - 1][j + 1] * (1 - fpw(1 - p[i], j + 1)); 
    printf("%.6lf\n", ans); 
  }
  return 0; 
}