POJ 2151 Check the difficulty of problems——概率dp

POJ 2151 Check the difficulty of problems——概率dp

题意：

一场区域赛的题目是合格的当且仅当每个队伍至少做1道题且冠军至少做n道题。

现在给出一场区域赛的题目数量m，队伍数量t，以及每支队伍通过每道题的概率，问这场区域赛题目是合格的概率为多少

思路：

对于一支队伍，定义dp[i][j]为前i个题通过了j道的概率，根据状态转移求出所有状态。

定义ans1=∑(1<=j<=m)dp[i][j], ans2=求和(1<=j<=n-1)dp[i][j]

那么对于所有队伍，最终答案就是所有队伍的ans1的乘积-所有队伍ans2的乘积

#include #include #include #include using namespace std;const int maxn = 50;const int maxm = 1010;int m, t, n;double p[maxn], ans[maxm][2], dp[maxn][maxn];int main() { while (~scanf("%d%d%d", &m, &t, &n) && m+t+n) { memset(ans, 0, sizeof(ans)); for (int k = 1; k <= t; k++) { for (int i = 1; i <= m; i++) scanf("%lf", &p[i]); memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 0; i < m; i++) { for (int j = 0; j <= i; j++) { dp[i+1][j+1] += p[i+1]*dp[i][j]; dp[i+1][j] += (1-p[i+1])*dp[i][j]; } } for (int i = 1; i <= m; i++) ans[k][0] += dp[m][i]; for (int i = 1; i < n; i++) ans[k][1] += dp[m][i]; } double ans1 = 1, ans2 = 1; for (int k = 1; k <= t; k++) { ans1 *= ans[k][0]; ans2 *= ans[k][1]; } printf("%.3lf\n", ans1-ans2); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。