[HNOI2015]亚瑟王
题目
解法
设\(dp[i][j]\)表示全局结束后，前\(i\)个中选了\(j\)个的概率,\(f[i]\)表示第\(i\)个被选上的概率，\(p[i]\)表示输入的那个概率。
有两种转移
1.这个数没被选,那么这个数一共会被考虑(r-j)次，因为选了前面\(j\)的那\(j\)轮没有考虑这个数，并且这(r-j)次都没有被选上,所以\[dp[i][j]+=dp[i-1][j]*(1-p[i])^{r-j}\]
2.这个数被选了,那么这个数一共会被考虑(r-j+1)次(因为前面有\(j-1\)个数被选，这\(j-1\)次没有考虑这个数)，没被选上的概率是\((1-p[i])^{r-j+1}\),所以被选上的概率是\(1-(1-p[i])^{r-j+1}\)。
\[dp[i][j]+=dp[i-1][j-1]*(1-(1-p[i])^{r-j+1})\]
\[f[i]+=dp[i-1][j-1]*(1-(1-p[i])^{r-j+1})\]
注意:第二种转移要特判\(j\ne 0\)
最后\(ans=\sum_{i=1}^nf[i]*d[i]\)
这个很显然，每一个被选的概率乘以伤害，全部加起来就是期望。
完整代码
#include<bits/stdc++.h>
using namespace std;
int n,m,d[221];
double dp[300][200],a[301][200],f[300];
int main(){int T;cin>>T;while(T--){cin>>n>>m;memset(dp,0,sizeof(dp));memset(f,0,sizeof(f));for(int i=1;i<=n;++i){scanf("%lf%d",&a[i][1],&d[i]);}for(int i=1;i<=n;++i){a[i][0]=1;a[i][1]=1-a[i][1];for(int j=2;j<=m;++j)a[i][j]=a[i][j-1]*a[i][1];}dp[1][0]=a[1][m];dp[1][1]=f[1]=1-dp[1][0];for(int i=2;i<=n;++i)for(int j=0;j<=m;++j){dp[i][j]+=dp[i-1][j]*a[i][m-j];if(j){dp[i][j]+=dp[i-1][j-1]*(1-a[i][m-j+1]);f[i]+=dp[i-1][j-1]*(1-a[i][m-j+1]);}}double ans=0;for(int i=1;i<=n;++i)ans+=f[i]*d[i];printf("%.10lf\n",ans);}
}