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})$$

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.