(\)
(Description)
有(N)张有顺序排好的牌，每张牌有伤害值(v_i)和发动概率(p_i)，游戏进行(K)轮，每轮都按顺序扫描，按照以下规则：
-
若当前牌在前面的轮中未发动过：
-
以(p_i)的概率发动，造成(v_i)的伤害，结束该轮；
-
以(1-p_i)的概率不发动，扫描下一张牌，若是最后一张就结束该轮；
-
-
若当前牌在前面的轮中发动过：
- 扫描下一张牌，若是最后一张就结束该轮。
求出这一套卡牌在这(K)轮游戏中能造成的总伤害的期望。 (T)组测试数据。
- (Tin [1,444],Nin [1,220],Kin[0,132],p_iin[0,1],v_iin[0,1000])
(\)
(Solution)
-
每张牌造成的伤害是固定且独立的，根据期望的线性性，总的期望等于每张牌的期望之和，每张牌的期望等于这张牌发动的概率乘以造成的伤害。而伤害是固定的，所以只需要求出每张牌被发动的概率就好。
-
这个(DP)思路还是很可以的
虽然最后还是抄了题解。他并没有将每一轮分开考虑，而是直接考虑全部的(K)轮。同时，他没有对每一张牌独立考虑，而是对一个前缀的所有牌放到一起考虑。设(f[i][j])表示在(K)轮中，前(i)张牌中发动了(j)张的概率。有边界(f[0][0]=1.0)，然后递推的时候分为第(i)张牌是否发动考虑：-
不发动((j<i))：所以前( i-1)张牌里发动了(j)张，这部分的概率是(f[i-1][j])。然后考虑当前不发动的限制，前(i-1)张中的发动的那(j)张对应的回合里，发动之后这一轮就结束了，所以当前位置没有被考虑到的可能，不发动的概率为(1)，而剩下在后(N-i)张里，有(K-j)张要被发动，他们都经过了第(i)张的位置，这些回合中第(i)张牌不能发动，所以有
[f[i][j]+=f[i-1][j] imes(1-p_i)^{K-j} ] -
发动((j ot=0))：前(i-1)张中发动了(j-1)张(f[i-1][j-1])。同样的思路那(j)张牌对应的位置不会考虑到当前牌，当前牌在剩下的(K-j+1)轮里挑一轮发动就好了。而容斥起来非常麻烦，用常用的与或转化，不发动是与的条件，所以发动的概率为((1-(1-p_i)^{K-j+1}))，所以有
[f[i][j]+=f[i-1][j-1] imes(1-(1-p_i)^{K-j+1}) ]
-
-
考虑如何组合出每一张牌发动的概率，跟第二类转移的思路类似，设(q_i)表示第(i)张牌在这(K)轮中发动的概率，前面发动任意张数都不需要考虑当前位置，在剩下的轮里挑一轮发动就好了
[q_i=sum_{j=1}^{min(i,K)-1} f[i-1][j] imes (1-(1-p_i)^{K-j}) ] -
根据期望的线性性有(E(sum)=sum_{i=1}^n q_i imes v_i)。
(\)
(Code)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 300
#define R register
#define gc getchar
using namespace std;
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
inline double rdd(){
double x=0,base=1; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=x*10+(c^48);c=gc();}
if(c=='.'){
c=gc();
while(isdigit(c)){x+=(base/=10)*(c^48);c=gc();}
}
return f?-x:x;
}
int n,m,val[N];
double p[N],mul[N][N],f[N][N];
inline void work(){
n=rd(); m=rd();
for(R int i=1;i<=n;++i) p[i]=rdd(),val[i]=(double)rd();
for(R int i=1;i<=n;++i){
mul[i][0]=1.0; f[i][0]=0;
for(R int j=1;j<=m;++j) f[i][j]=0,mul[i][j]=mul[i][j-1]*(1.0-p[i]);
}
f[0][0]=1.0;
for(R int i=1;i<=n;++i)
for(R int j=0;j<=min(i,m);++j){
if(j) f[i][j]+=f[i-1][j-1]*(1.0-mul[i][m-j+1]);
if(i!=j) f[i][j]+=f[i-1][j]*mul[i][m-j];
}
R double ans=0.0,cnt=0.0;
for(R int i=1;i<=n;++i){
cnt=0.0;
for(R int j=0;j<=min(i-1,m);++j) cnt+=f[i-1][j]*(1.0-mul[i][m-j]);
ans+=cnt*val[i];
}
printf("%.10lf
",ans);
}
int main(){
int t=rd();
while(t--) work();
return 0;
}