题解
利用期望的线性性，可以把问题转化为求每一个卡牌造成期望的期望值。
然后我们就需要知道每一个卡牌发动技能的概率。
因为当某一张卡牌发动技能时这一轮会结束，这就很难直接计算了。
我们使用DP
设dp[i][j]为前i张卡牌在r轮中有j张发动技能的概率
i这张牌发动技能的概率就为sigema(j=1,min(r,i-1))f[i-1][j]*(1-(1-p[i])^(m-j))
然后我们考虑如何转移。
当当前卡牌发动技能，dp[i][j]+=dp[i-1][j-1]*(1-(1-p[i])^(m-j+1))
当当前卡牌不发动技能,dp[i][j]+=dp[i-1][j]*(1-p[i])^(m-j)
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int N=300; 8 int t,n,m; 9 double p[N],d[N],pw[N][N],dp[N][N],g[N],ans; 10 int main(){ 11 scanf("%d",&t); 12 while(t--){ 13 memset(dp,0,sizeof(dp)); 14 memset(g,0,sizeof(g)); 15 scanf("%d%d",&n,&m); 16 for(int i=1;i<=n;i++){ 17 scanf("%lf%lf",&p[i],&d[i]); 18 pw[i][0]=1; 19 } 20 for(int i=1;i<=n;i++) 21 for(int j=1;j<=m;j++){ 22 pw[i][j]=pw[i][j-1]*(1.0-p[i]); 23 } 24 dp[1][0]=pw[1][m]; 25 dp[1][1]=g[1]=1.0-pw[1][m]; 26 for(int i=2;i<=n;i++) 27 for(int j=0;j<=min(i,m);j++){ 28 if(j!=0)dp[i][j]+=(1-pw[i][m-j+1])*dp[i-1][j-1]; 29 if(i!=j)dp[i][j]+=pw[i][m-j]*dp[i-1][j]; 30 } 31 for(int i=2;i<=n;i++) 32 for(int j=0;j<=min(i-1,m);j++){ 33 g[i]+=dp[i-1][j]*(1.0-pw[i][m-j]); 34 } 35 ans=0; 36 for(int i=1;i<=n;i++){ 37 ans+=g[i]*d[i]; 38 } 39 printf("%.10lf ",ans); 40 } 41 return 0; 42 }