Description
玩家有一套卡牌，共 n张。游戏时，玩家将 n 张卡牌排列成某种顺序，排列后
将卡牌按从前往后依次编号为 1 ~ n。本题中，顺序已经确定，即为输入的顺序。
每张卡牌都有一个技能。第 i 张卡牌的技能发动概率为 pi，如果成功发动，则会对
敌方造成di点伤害。也只有通过发动技能，卡牌才能对敌方造成伤害。基于现实因
素以及小K非洲血统的考虑，pi不会为 0，也不会为 1，即 0 < pi < 1。
一局游戏一共有 r 轮。在每一轮中，系统将从第一张卡牌开始，按照顺序依次
考虑每张卡牌。在一轮中，对于依次考虑的每一张卡牌：
1如果这张卡牌在这一局游戏中已经发动过技能：
1.1 如果这张卡牌不是最后一张，则跳过之（考虑下一张卡牌）；
否则（是最后一张），结束这一轮游戏。
2否则（这张卡牌在这一局游戏中没有发动过技能），设这张卡牌为第 i 张
2.1将其以 pi的概率发动技能。
2.2如果技能发动，则对敌方造成 di点伤害，并结束这一轮。
2.3如果这张卡牌已经是最后一张（即 i 等于n），则结束这一轮；
否则，考虑下一张卡牌。
请帮助小 K 求出这一套卡牌在一局游戏中能造成的伤害的期望值。
期望DP。
但是这道题并不直接将上代的期望当成目标的DP状态，而是概率。最后乘上一个伤害。
对于一系列事件，并且发生有先后顺序，发生过了就不能再发生的概率题都可用此解法。
由于全面时间对后面时间有影响的galvan，一般都从后向前推，即DP状态表示的是后面剩余的事件即（也见到过还能得到的期望这种神一样的状态）。
DP状态：
f[i][j]:在区间[i,n]经历了j次考虑轮回的概率。
考虑第i-1号物品的转移。
如果一直没有没有选：f[i][j]+=f[i-1][j](1-p[i-1])j
如果在一次中选啦：f[i][j]+=f[i-1][j+1](1-(1-p[i-1])j+1)
得到DP方程。然后初始状态f[1][r]=1;
然后由于每个j对应的方案都各不相同，所以到达每个物品前面的f[i][j]各不冲突，每个f[i][j]*在j次机会中能发动i的概率之和就是能发动该技能的和概率。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int T,n,r;
int d[300];
double p[300],ans;
double f[240][140];
double pow(double x,int y)
{
double re=1.0;
while(y)
{
if(y&1) re*=x;
x*=x;y>>=1;
}
return re;
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(f,0,sizeof(f));
scanf("%d%d",&n,&r);
for(int i=1;i<=n;i++)
scanf("%lf%d",&p[i],&d[i]);
f[0][r]=1.0;ans=0.0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=r;j++)
{
f[i][j]=f[i-1][j]*pow(1-p[i-1],j)+f[i-1][j+1]*(1-pow(1-p[i-1],j+1));
ans+=f[i][j]*(1-pow(1-p[i],j))*d[i];
}
}
printf("%.10lf\n",ans);
}
return 0;
}