Check the difficulty of problems

题目大意:


有m场比赛,t个队伍,告诉你每个队伍每场比赛的胜率,求所有队伍获胜一场及以上且冠军队伍获胜n场及以上的概率。

思路:


很明显的概率 d p dp dp;

先定义:

d p [ i ] [ j ] dp[i][j] dp[i][j] 为第 i i i个队伍在前 j j j道题中恰好做了 k k k道题的概率。

因为题意要求所有队伍获胜一场及以上且冠军队伍获胜n场及以上的概率;

所以我们还需要一个数组 f [ i ] [ j ] f[i][j] f[i][j] 来存储第 i i i个队至多做出 j j j题的概率。

接下来分析概率情况:

对于任意队伍而言,一道题只有两种结果:

做对 or 没做对

那么状态转移方程就很好想了 :

  • p 1 = d p [ i ] [ j − 1 ] [ k − 1 ] ∗ p [ i ] [ j ] p1 = dp[i][j - 1][k - 1] * p[i][j] p1=dp[i][j−1][k−1]∗p[i][j];
  • p 2 = d p [ i ] [ j − 1 ] [ k ] ∗ ( 1 − p [ i ] [ j ] ) p2 = dp[i][j - 1][k] * (1 - p[i][j]) p2=dp[i][j−1][k]∗(1−p[i][j]);
  • d p [ i ] [ j ] [ k ] = p 1 + p 2 dp[i][j][k] = p1 + p2 dp[i][j][k]=p1+p2;

解释:

  • p 1 p1 p1 :第 j j j 到题做对,此时一共做对 k k k 道题,因此需要乘上 d p [ i ] [ j − 1 ] [ k − 1 ] dp[i][j - 1][k - 1] dp[i][j−1][k−1] ( i i i队在前 j − 1 j - 1 j−1 场比赛做对 k − 1 k - 1 k−1 道题的概率);
  • p 2 p2 p2 参考 p 1 p1 p1 的解释;
  • 总概率为两种情况概率的总和。

最终答案:


因为 d p dp dp 的状态定义,最终结果的求解方法自然而然地选择了排除法(即用总概率 − - − 不符合情况的概率

  • 总概率 :$ \prod_{i=1}^t (f[i][m] - f[i][0])$ ;
  • 不符合情况的概率:$ \prod_{i=1}^t (f[i][n - 1] - f[i][0])$ ;

解释:

  • 总概率:共有 m m m 场比赛,那么所有符合题意的情况的概率就为 t t t 个队伍做对 1 1 1 到 m m m 道题的概率之积,用至多作对 m m m 道题的概率减去至多做对 0 0 0 道题的概率,即为做对 1 1 1 到 m m m 道题的概率
  • 不符合情况的概率:参考总概率的解释

完整代码:
P S PS PS:注意初始化!!!


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 150;
int n,m,t;
double dp[1005][35][35],f[1005][1005],p[1005][35];
//p[i][j] 第i个队通过第j题的概率
int main() {
	while(scanf("%d %d %d",&m,&t,&n) != EOF && m != 0 && t != 0 && n != 0) {
		memset(dp,0,sizeof(dp));
		memset(f,0,sizeof(f));
		for(int i = 1; i <= t; i ++) {
			for(int j = 1; j <= m; j ++) scanf("%lf",&p[i][j]);
		}
		for(int i = 1; i <= t; i ++) {
			dp[i][0][0] = 1;//一道题没做 
			for(int j = 1; j <= m; j ++) {
				dp[i][j][0] = dp[i][j - 1][0] * (1 - p[i][j]); //没做对题 
			}
		}
		for(int i = 1; i <= t; i ++) {
			for(int j = 1; j <= m; j ++) {
				for(int k = 1; k <= j; k ++) {
					dp[i][j][k] = dp[i][j - 1][k - 1] * p[i][j] + dp[i][j - 1][k] * (1 - p[i][j]);//两种情况:第j道题做对和没做对 
				}
			}
		}
		for(int i = 1; i <= t; i ++) {
			for(int j = 0; j <= m; j ++) {
				if(j != 0 ) f[i][j] = f[i][j - 1] + dp[i][m][j]; 
				else f[i][j] = dp[i][m][0];
			}
		}
		double p1 = 1, p2 = 1;
		for(int i = 1; i <= t; i ++) {
			p1 *= (f[i][m] - f[i][0]); 
			p2 *= (f[i][n - 1] - f[i][0]);
		}
		printf("%.3lf\n",p1 - p2);
	}
	return 0;
}
上一篇:【CVX】SDP and conic form problems


下一篇:【leetcode】高频题目整理_排序篇( High Frequency Problems, Sort )