【POJ】2151 Check the difficulty of problems

题意：T个队伍M条题目，给出每个队伍i的每题能ac的概率p[i][j]，求所有队伍至少A掉1题且冠军至少A掉N题的概率（T<=1000, M<=30）

#include <cstdio>

#include <cstring>

using namespace std;

const int T=1005, M=35;

double d[T][M], p[T][M];

int n, m, N;

void clr() {

	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) d[i][j]=0;

}

int main() {

	while(scanf("%d%d%d", &m, &n, &N), !(m==0&&n==0&&N==0)) {

		for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) scanf("%lf", &p[i][j]);

		for(int i=1; i<=n; ++i) d[i][0]=1;

		for(int i=1; i<=n; ++i)

			for(int k=1; k<=m; d[i][0]*=1-p[i][k], ++k)

				for(int j=m; j; --j) d[i][j]=d[i][j]*(1-p[i][k])+d[i][j-1]*p[i][k];

		//for(int i=1; i<=n; ++i) { for(int j=0; j<=m; ++j) printf("%.2f ", d[i][j]); puts(""); }

		for(int i=1; i<=n; ++i) for(int j=m; j; --j) d[i][j]+=d[i][j+1];

		double ans=0, sum;

		for(int i=1; i<=n; ++i) {

			sum=d[i][N];

			for(int j=1; j<i; ++j) sum*=(d[j][1]-d[j][N]);

			for(int j=i+1; j<=n; ++j) sum*=d[j][1];

			ans+=sum;

		}

		printf("%.3f\n", ans);

		clr();

	}

	return 0;

}

我们只需要设状态就行了= =随便搞...

设f[i][j][k]表示第i队解决j~k个问题的概率

$$ans=\sum_{i} \left( f[i][N][M] * \prod_{j<i} f[j][1][N-1] * \prod_{j>i} f[j][1][M] \right) $$

这样就能不重不漏....（不难理解，我觉得这个很简单的吧= =

然后我们来一发前缀和，d[i][j]表示第i队解决至少j个问题的概率

$$ans=\sum_{i} \left( d[i][N] * \prod_{j<i} ( d[j][1]-d[j][N] ) * \prod_{j>i} d[j][1] \right) $$

问题转化为如何求d[i][j]...

设d'[i][j]表示第i队解决j个问题的概率

我们类似背包依次加入每个问题，有

d[i][j]=d[i][j]*(1-p[i][k])+d[i][j-1]*p[i][k]（自己好好思考= =，我拐了好多个弯才想出来QAQ

于是就ok了。。。

巴特西

【POJ】2151 Check the difficulty of problems

最新文章

热门文章