BZOJ 4008

传送门

题目意思大概就是在$n$张卡牌中挑$1-r$张,每张只能挑一次,求选出的卡牌的期望总伤害

设$F[i,j]$为选至第$i$张,还能选$j$次的期望伤害值

每张牌有选与不选两种情况,所以

$$F_{i,j}=F_{i-1,j}\cdot(1-p_i)^j+F_{i-1,j+1}\cdot(1-(1-p_i)^{j+1})$$


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
program bzoj_4008;
var g,f:array[0..221,0..133]of extended;
t,n,r,i:longint;
p:array[1..220]of extended;
d:array[1..220]of longint;
ans:extended;

procedure calc;
var i,j:longint;
a,b:extended;
begin
for i:=1 to n do
for j:=1 to r do g[i,j]:=g[i,j-1]*(1-p[i]);
ans:=0;
fillchar(f,sizeof(f),0);
f[0,r]:=1;
for i:=1 to n do
for j:=0 to r do
begin
a:=f[i-1,j]*g[i,j];
b:=f[i-1,j+1]*(1-g[i,j+1]);
f[i,j]:=a+b;
ans:=ans+b*d[i];
end;
end;

begin
readln(t);
fillchar(g,sizeof(g),0);
for i:=1 to 220 do g[i,0]:=1;
for t:=1 to t do
begin
readln(n,r);
for i:=1 to n do readln(p[i],d[i]);
calc;
writeln(ans:0:10);
end;
end.