解析

顯然可以利用期望的線性性對(duì)每張牌單獨(dú)計(jì)算貢獻(xiàn)。
現(xiàn)在的關(guān)鍵就是如何求出每張牌被使用的概率。

考慮第 $i$ 張牌，如果它的前面 $[1,i?1]$ 中有 $j$ 張牌被使用，那么它被使用的概率就是 $1?(1?p_i{)}^{r?j}$。
根據(jù)這個(gè)，設(shè)計(jì) $f_{i,j}$ 表示前 $i$ 張牌中使用了 $j$ 張的概率，也不難進(jìn)行轉(zhuǎn)移：
$$f_{i,j}=f_{i?1,j?1}(1?(1?p_i{)}^{r?j})+f_{i?1,j}?(1?p_i{)}^{r?j+1}$$
求出 $f$ 后再用其求出每張牌的概率即可。
預(yù)處理 $(1?p_i{)}^k$，時(shí)間復(fù)雜度 $O(Tnr)$。

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("ok\n") inline ll read(){ll x(0),f(1);char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return f*x; }const int N=250; const int mod=1e9+7;int n,m; double p[N],f[N][N],mi[N][N]; int d[N]; void work(){n=read();m=read();for(int i=1;i<=n;i++) scanf("%lf%d",&p[i],&d[i]); for(int i=1;i<=n;i++){mi[i][0]=1;for(int j=1;j<=m;j++) mi[i][j]=mi[i][j-1]*(1-p[i]);}f[0][0]=1;for(int i=1;i<=n;i++){f[i][0]=f[i-1][0]*mi[i][m];for(int j=1;j<=i;j++){f[i][j]=f[i-1][j-1]*(1-mi[i][m-j+1])+f[i-1][j]*mi[i][m-j];}}double ans(0);for(int i=1;i<=n;i++){for(int j=1;j<=i;j++) ans+=d[i]*f[i-1][j-1]*(1-mi[i][m-j+1]);}printf("%.10lf\n",ans); } signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifint T=read();while(T--) work();return 0; } /* */ 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的P3239 [HNOI2015]亚瑟王（期望）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。