POJ2151Check the difficulty of problems 概率DP

一開始感觉是个二维的，然后推啊推啊没有推出来，一開始觉得冠军队伍仅仅能有一个。所以必须控制一个队伍解题数比其他队伍多，并且这个冠军队伍解题数必须大于等于n。大于n的时候其他队伍解题数就非常难了，直到坑到最后才发现 原来能够非常多队伍都是冠军，大家都是十道 那么大家都是冠军。…………

然后还是继续推二维，结果还是没想出。看来不是先如果方程才好做的，先整体来考虑，全部队伍出题概率，就是1 -减去没出题的概率。没出题的概率非常easy的，每一个队伍每道题都做不出 的概率累乘就能够了。那么冠军队伍至少出n道要怎么求呢，想了半天也没想好。后来发现直接 出题的概率 减去 每一个队伍出题数目是在 1到n-1之间的概率累乘。 就能够了，为什么呢？首先每一个队伍都出题这个条件已经满足了，剩下的反过来想。如果每一个队伍出题数都在1到n-1之间那么 就不符合题目要求了。那么减去这部分答案就能够了，这样想就简单点了

后来还是想推二维。发现想不出来，最后推了一个三维的 

dp[i][j][k]代表第i仅仅队伍前j道题解出了k道

边界dp[i][0][0] = 1,能够这么理解，前0道题目除了0道题目 这是肯定的 所以概率为1

后来不服。又强行推了一个二维的，如果好方程以后发现 跟三维的意义一样嘛，看来还是要先主要的弄清楚了才干够
先贴个三维的

int m,t,n;

double mp[1000 + 55][50 + 55];

double dp[1000 + 55][30 + 5][30 + 5];//dp[i][j][k]第i队前j道题做出k道


void init() {
	memset(mp,0.00,sizeof(mp));
	memset(dp,0.00,sizeof(dp));
}

bool input() {
	while(cin>>m>>t>>n,n + m + t) {
		for(int i=1;i<=t;i++)
			for(int j=1;j<=m;j++)
				cin>>mp[i][j];
		return false;
	}
	return true;
}

void cal() {
	for(int i=1;i<=t;i++) {//边界处理
		dp[i][0][0] = 1.00;
		for(int j=1;j<=m;j++) 
			dp[i][j][0] = dp[i][j - 1][0] * (1 - mp[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] * mp[i][j] + dp[i][j - 1][k] * (1 - mp[i][j]);
		}
	}
	double qq = 1.00;
	for(int i=1;i<=t;i++)qq *= (1 - dp[i][m][0]);//dp[i][m][0]表示i队一道题都没做出。减去就是出题了
	double pp = 1.00;
	double tmp = 0.00;
	for(int i=1;i<=t;i++) {
		tmp = 0.00;
		for(int k=1;k<=n - 1;k++)tmp += dp[i][m][k];//i队出了1道，2道……（n - 1）道的概率
		pp *= tmp;
	}
	double ans = qq - pp;
	printf("%.3lf\n",ans);
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}

int m,t,n;

double mp[1000 + 55][50 + 55];

double dp[30 + 5][30 + 5];//dp[j][k]前j道题做出k道


void init() {
	memset(mp,0.00,sizeof(mp));
	memset(dp,0.00,sizeof(dp));
}

bool input() {
	while(cin>>m>>t>>n,n + m + t) {
		for(int i=1;i<=t;i++)
			for(int j=1;j<=m;j++)
				cin>>mp[i][j];
		return false;
	}
	return true;
}

void cal() {
	dp[0][0] = 1.00;
	double qq = 1.00;
	double pp = 1.00;
	for(int i=1;i<=t;i++) {
	for(int j=1;j<=m;j++)
		dp[j][0] = dp[j - 1][0] * (1 - mp[i][j]);
		for(int j=1;j<=m;j++) {
			for(int k=1;k<=m;k++) {
				dp[j][k] = dp[j - 1][k] * (1 - mp[i][j]) + dp[j - 1][k - 1] * mp[i][j];
			}
		}
		qq *= (1 - dp[m][0]);//当前队伍出题的概率，全部队伍累乘
		double tmp = 0.00;
		for(int k=1;k<=n - 1;k++)tmp += dp[m][k];//当前队伍出题数目在[1,n)之间的概率
		pp *= tmp;//全部队伍要累乘
	}
	double ans = qq - pp;//减减就是答案
	printf("%.3lf\n",ans);
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5252724.html，如需转载请自行联系原作者