题面：亚瑟王
最近考试考期望很自闭啊，没做过这种类型的题，只能现在练一练；
所谓期望，就是状态乘上自己的概率；对于这道题来说，我们要求的是每张牌的伤害乘上打出的概率的和；
当然不是直接乘，因为给的是每轮中这张牌打出的概率，这张牌没打出就要考虑下一张牌，要有一张牌发出技能才能结束一轮；除非一张牌都发不出来；
设每张牌打出的概率是exp[]，答案就是exp[i]*d[i];
exp[i]怎么求？
我们要始终在概率面前一视同仁；
设f[i][j]为前i张牌打出j张牌的概率，分别由f[i-1][j-1]和f[i-1][j]转移过来，这张牌打出去和这张牌没打出去；
这张牌打出去了，那么j-1轮中他扔不出去，r-j+1轮中他扔了出去，即为f[i-1][j-1]*(1-(1-p[i])r-j+1)；
(1-p[i])r-j+1 是剩下的都没打出的概率，用1减去即是j轮打出的概率；
j轮打不出的概率就是f[i-1][j]*(1-(1-p[i])r-j )
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=222; typedef double dd; int T; int n,r; dd p[maxn]; int d[maxn]; dd ksm_p[maxn][maxn]; void pre_p() { for(int i=1;i<=n;i++) { ksm_p[i][0]=1; for(int j=1;j<=r;j++) { ksm_p[i][j]=ksm_p[i][j-1]*(1-p[i]); } } } dd ans; dd f[maxn][maxn];//i card j used dd exp[maxn]; int main() { scanf("%d",&T); while(T--) { ans=0; memset(f,0,sizeof(f)); memset(exp,0,sizeof(exp)); scanf("%d%d",&n,&r); for(int i=1;i<=n;i++) { scanf("%lf%d",&p[i],&d[i]); } pre_p(); f[1][0]=ksm_p[1][r]; f[1][1]=exp[1]=1.0-ksm_p[1][r]; for(int i=2;i<=n;i++) { for(int j=0;j<=r;j++) { if(j>i) break; if(j!=i) exp[i]+=f[i-1][j]*(1-ksm_p[i][r-j]); if(j) f[i][j]+=f[i-1][j-1]*(1-ksm_p[i][r-j+1]); if(i!=j) f[i][j]+=f[i-1][j]*ksm_p[i][r-j]; } } for(int i=1;i<=n;i++) ans+=exp[i]*d[i]; printf("%.10lf\n",ans); } return 0; }
原文：https://www.cnblogs.com/WHFF521/p/11628627.html