BZOJ 4008.「HNOI2015」亚瑟王

一道有思维难度的期望 DP。
根据期望的线性性,可以算出每张牌发动的概率然后乘伤害最后加起来。

fif_i 表示第 ii 张牌发动的概率。
首先有 f1=(1(1p1)r)f_1 = (1 - (1 - p_1)^r)

我们发现一张牌发动的概率跟之前已经发动了几张牌有关。
所以可以设 gi,jg_{i,j} 表示前 ii 张牌,总共发动了 jj 张(第 ii 张不一定发动)。

转移,只需要考虑第 ii 张牌是否发动即可。

fi,j=(1(1ai)rj+1)fi1,j1+(1ai)rjfi1,jf_{i,j} = (1 - (1 - a_i)^{r - j + 1}) f_{i - 1,j - 1} + (1 - a_i)^{r - j} f_{i - 1,j}

第一项对应发动,第二项对应不发动。

然后要预处理所有 (1ai)j(1 - a_i)^j,并且特判 r=0r = 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
#include <cstdio>
#include <cstring>
#include <algorithm>
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);
}
}