BZOJ

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.