POJ2151-Check the difficulty of problems(概率DP)
The of DP check 概率 problems
2023-09-27 14:27:04 时间
Check the difficulty of problems
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 4512 | Accepted: 1988 |
Description
Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms:
1. All of the teams solve at least one problem.
2. The champion (One of those teams that solve the most problems) solves at least a certain number of problems.
Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem.
Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 <= i <= T, 1<= j <= M). Well, can you calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems?
1. All of the teams solve at least one problem.
2. The champion (One of those teams that solve the most problems) solves at least a certain number of problems.
Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem.
Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 <= i <= T, 1<= j <= M). Well, can you calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems?
Input
The input consists of several test cases. The first line of each test case contains three integers M (0 < M <= 30), T (1 < T <= 1000) and N (0 < N <= M). Each of the following T lines contains M floating-point numbers in the range of [0,1]. In these T lines,
the j-th number in the i-th line is just Pij. A test case of M = T = N = 0 indicates the end of input, and should not be processed.
Output
For each test case, please output the answer in a separate line. The result should be rounded to three digits after the decimal point.
Sample Input
2 2 2 0.9 0.9 1 0.9 0 0 0
Sample Output
0.972
题意:
有T支队伍參加比赛,比赛一共同拥有M道题,要求算出第一名要至少做出N道题,且其它队伍都做出题目的概率
做法:
先算出每一个队伍至少做出一题的概率,然后减去全部队解题数都小于N题且大于1题的概率,即为所求。
非常easy的概率DP,DP[i][j]表示一支队伍解前i道题,解出j题的概率,递推就可以
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int M,T,N; double p[1010][40]; double dp[40][40]; int main(){ while(~scanf("%d%d%d",&M,&T,&N) && N+T+M){ double all = 1.0; for(int i = 0; i < T; i++){ double t = 1.0; for(int j = 0; j < M; j++){ scanf("%lf",&p[i][j]); t *= (1-p[i][j]); } all *= (1-t); } double no = 1.0; for(int i = 0; i < T; i++){ dp[0][0] = 1-p[i][0]; dp[0][1] = p[i][0]; for(int j = 1; j < M; j++){ dp[j][0] = dp[j-1][0]*(1-p[i][j]); for(int k = 1; k <= j+1; k++){ dp[j][k] = dp[j-1][k]*(1-p[i][j])+dp[j-1][k-1]*p[i][j]; } } double t = 0.0; for(int j = 1; j < N; j++){ t += dp[M-1][j]; } no *= t; } printf("%.3f\n",all-no); } return 0; }
相关文章
- The Zen of Python
- Cause: ...OutputBuildAction has been compiled by a more recent version of the Java Runtime (class file version 55.0), this version of the Java Runtime only recognizes class file versions up to 52.0
- android 因为没有赋null,报以下错:has already been added to the window manager
- Java compiler level does not match the version of the installed Java project facet解决办法
- Java 工程连接 Elasticsearch 报NoNodeAvailableException[None of the configured nodes are available
- 确定聚类数(Determining the Number of Clusters)
- continue — Skip to the next iteration of a loop in a shell script
- Beginning Python chapter 1 Instant Hacking The Basics 2: Comments Strings
- The Seven Tools of Causal Inference, with Reflections on Machine Learning
- Better Together: The Power of IoT and AR for Enterprises
- 南阳ccpc C题 The Battle of Chibi && hdu5542 The Battle of Chibi (树状数组优化+dp)
- 南阳ccpc C题 The Battle of Chibi 树状数组+dp
- 【2020杭电多校】 Lead of Wisdom、The Oculus
- NR CSI(二) the workflow of CSI report
- Harry Potter and the Prisoner of Azkaban
- 封神台 第六章:GET THE PASS!(进程中抓下管理员明文密码)
- Eclipse 报 "The builder launch configuration could not be found" 错误
- 嵌入式 hi3518c下ramdisk文件系统与文件系统烧写以及uboot中change-the-env
- Exception thrown by the agent : java.rmi.server.ExportException: Port already in use
- 2019-8-31-How-to-output-the-target-message-in-dotnet-build-command-line