一道有思维难度的期望 DP。
根据期望的线性性，可以算出每张牌发动的概率然后乘伤害最后加起来。
设 \(f_i\) 表示第 \(i\) 张牌发动的概率。
首先有 \(f_1 = (1 - (1 - p_1)^r)\)。
我们发现一张牌发动的概率跟之前已经发动了几张牌有关。
所以可以设 \(g_{i,j}\) 表示前 \(i\) 张牌，总共发动了 \(j\) 张（第 \(i\) 张不一定发动）。
转移，只需要考虑第 \(i\) 张牌是否发动即可。
有 \[f_{i,j} = (1 - (1 - a_i)^{r - j + 1}) f_{i - 1,j - 1} + (1 - a_i)^{r - j} f_{i - 1,j}\]
第一项对应发动，第二项对应不发动。
然后要预处理所有 \((1 - a_i)^j\)，并且特判 \(r = 0\) 的情况。
代码： 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
using namespace std;
const int N = 220;
const int R = 132;
int T,n,r,d[N + 5];
double a[N + 5],f[N + 5],g[N + 5][R + 5],pw[N + 5][R + 5];
double ans;
int main()
{
scanf("%d",&T);
while(T--)
{
ans = 0;
scanf("%d%d",&n,&r);
for(register int i = 1;i <= n;++i)
{
scanf("%lf%d",a + i,d + i),pw[i][0] = 1;
for(register int j = 1;j <= r;++j)
pw[i][j] = pw[i][j - 1] * (1 - a[i]);
}
if(!r)
{
puts("0");
continue;
}
g[1][0] = pw[1][r],g[1][1] = f[1] = 1 - pw[1][r];
for(register int i = 2;i <= n;++i)
for(register int j = 0;j <= min(i,r);++j)
g[i][j] = (j ? (1 - pw[i][r - j + 1]) * g[i - 1][j - 1] : 0) + (i ^ j ? pw[i][r - j] * g[i - 1][j] : 0);
for(register int i = 2;i <= n;++i)
{
f[i] = 0;
for(register int j = 0;j <= min(i - 1,r);++j)
f[i] += g[i - 1][j] * (1 - pw[i][r - j]);
}
for(register int i = 1;i <= n;++i)
ans += f[i] * d[i];
printf("%.10f\n",ans);
}
}