原题传送门 令 p i p_i pi表示第 i i i个技能的概率 a n s = ∑ p i ∗ d i ans=\sum p_i*d_i ans=∑pi∗di
令 d p i , j dp_{i,j} dpi,j表示前 i i i个技能，成功了 j j j个的概率 d p i , j = d p i − 1 , j ∗ ( 1 − p i ) r − j + d p i − 1 , j − 1 ∗ [ 1 − ( 1 − p i ) r − j + 1 ] dp_{i,j}=dp_{i-1,j}*(1-p_i)^{r-j}+dp_{i-1,j-1}*[1-(1-p_i)^{r-j+1}] dpi,j=dpi−1,j∗(1−pi)r−j+dpi−1,j−1∗[1−(1−pi)r−j+1] p i = ∑ d p i − 1 , j ∗ [ 1 − ( 1 − p i ) r − j ] p_i=\sum dp_{i-1,j}*[1-(1-p_i)^{r-j}] pi=∑dpi−1,j∗[1−(1−pi)r−j]
Code：
#include <bits/stdc++.h> #define maxn 251 using namespace std; double p[maxn], dp[maxn][maxn], power[maxn][maxn], d[maxn]; int n, m; int main(){ int T; scanf("%d", &T); while (T--){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i){ scanf("%lf%lf", &p[i], &d[i]); power[i][0] = 1; for (int j = 1; j <= m; ++j) power[i][j] = power[i][j - 1] * (1 - p[i]); } dp[0][0] = 1; for (int i = 1; i <= n; ++i) for (int j = 0; j <= i; ++j){ dp[i][j] = dp[i - 1][j] * power[i][m - j]; if (j) dp[i][j] += dp[i - 1][j - 1] * (1 - power[i][m - j + 1]); } double ans = 0; for (int i = 1; i <= n; ++i){ double s = 0; for (int j = 0; j <= i - 1; ++j) s += dp[i - 1][j] * (1 - power[i][m - j]); ans += s * d[i]; } printf("%.10lf\n", ans); } return 0; }