小 K 不慎被 LL 邪教洗脑了，洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。
输入文件的第一行包含一个整数 T，代表测试数据组数。
对于每组数据，输出一行，包含一个实数，为这套卡牌在这一局游戏中造成的伤害的期望值。对于每一行输出，只有当你的输出和标准答案的相对误差不超过10^-8时——即|a-o|/a<=10-8时(其中a是标准答案，o是输出)，你的输出才会被判为正确。
一共有 13 种可能的情况：
正解：概率dp。
这道题太难了qwq。。蒟蒻表示看题解都懵懵懂懂。。
来自clos的题解：
由于期望的可加性，我们可以分解这个期望，所以现在模型转为求每张牌发动的概率。由于是对于每张牌，所以第几轮就不重要了，重要的只是它是否在某一轮发动了。
这个想法给了我们一个dp的思路，不妨再次抽出一个模型：一开始有r次机会，然后一次考虑每个人，对于每次机会，有pi的概率给这个人，如果某次机会给了这个人，就跳过这个人，然后总的机会数目-1。求每个人分到一个机会的概率。
那么就可以令f[i][j]表示考虑完第i个人还剩j次机会的概率，初值是f[0][r]=1，转移就是f[i][j]以(1-p[i+1])^j转移到f[i+1][j]表示没有一次机会给这个人；以1-(1-p[i+1])^j转移到f[j+1][j-1]。然后就可以顺便算出每张牌发动的概率。预处理之后的复杂度是O(nrT)。
还有ljh2000的题解：
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 #define il inline 14 #define RG register 15 #define ll long long 16 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 17 18 using namespace std; 19 20 long double f[250][140],pp[250][140],P[250],p[250],d[250],ans; 21 int n,r; 22 23 il int gi(){ 24 RG int x=0,q=1; RG char ch=getchar(); while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 25 if (ch==‘-‘) q=-1,ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); return q*x; 26 } 27 28 il void work(){ 29 n=gi(),r=gi(); 30 for (RG int i=1;i<=n;++i) 31 scanf("%Lf%Lf",&p[i],&d[i]); 32 memset(pp,0,sizeof(pp)); 33 memset(P,0,sizeof(P)); 34 memset(f,0,sizeof(f)); 35 for (RG int i=0;i<=n;++i){ 36 pp[i][0]=1; 37 for (RG int j=1;j<=r;++j) 38 pp[i][j]=pp[i][j-1]*(1-p[i]); 39 } 40 ans=0,f[0][r]=1; 41 for (RG int i=1;i<=n;++i) 42 for (RG int j=1;j<=r;++j){ 43 f[i][j]=f[i-1][j]*pp[i-1][j]+f[i-1][j+1]*(1-pp[i-1][j+1]); 44 P[i]+=f[i][j]*(1-pp[i][j]); 45 } 46 for (RG int i=1;i<=n;++i) ans+=P[i]*d[i]; 47 printf("%0.10Lf\n",ans); return; 48 } 49 50 int main(){ 51 File("arthur"); 52 RG int T=gi(); 53 while (T--) work(); 54 return 0; 55 }
原文：http://www.cnblogs.com/wfj2048/p/6506200.html