//解释转的~~~~~~
『题目大意』
一次比赛中，共M道题，T个队，p[i][j]表示队i解出题j的概率；问每队至少解出一题且
冠军队至少解出N道题的概率。
『算法』
设a[i][j][k]表示第i队在前j道题中共解出k道题的概率，易得a[i][j][k]有如下递推
关系(另需考虑边界条件)：
a[i][j][k] = a[i][j-1][k-1] * p[i][j] + a[i][j-1][k] * (1-p[i][j])
设s[i][j]表示a[i][M][0] + a[i][M][1] + ... + a[i][M][j]
问题的解可以转化为：每队均至少做一题的概率（用P1表示）减去每队做题数均在1到N-1
之间的概率（用P2表示）。
P1 = (s[1][M] - s[1][0])*(s[2][M]-s[2][0])*...*(s[T][M]-s[T][0])
P2 = (s[1][N-1] - s[1][0])*(s[2][N-1]-s[2][0])*...*(s[T][N-1]-s[T][0])
『算法复杂度』
O(T*M^2)
『说明』
感谢UESTC的zhucheng在poj的提示！
#include<iostream>
using namespace std;
#define MM 30
#define MT 1000
double p[MT+1][MM+1];
double d[MT+1][MM+1][MM+1];
double MTO[MT+1]; //每队至少做出一题的概率
double LTN[MT+1];//少于N道，亦即1
N-1
int main()
{
int i,j,k;
int M,T,N;
double tmp1,tmp2;
while(scanf("%d%d%d",&M,&T,&N)!=EOF && M)
{
memset(MTO,0,sizeof(MTO));
memset(LTN,0,sizeof(LTN));
for(i=1;i<=T;i++)
for(j=1;j<=M;j++)
scanf("%lf",&p[i][j]);
for(i=1;i<=T;i++)
{
d[i][0][0]=1;
for(j=1;j<=M;j++)
{
d[i][j][0] = d[i][j-1][0]*(1-p[i][j]);
for(k=1;k<=M;k++)
d[i][j][k]=p[i][j]*d[i][j-1][k-1]+(1-p[i][j])*d[i][j-1][k];
}
}
tmp1=tmp2=1.0;
for(i=1;i<=T;tmp1*=MTO[i],i++)
for(k=1;k<=M;k++)
MTO[i]+=d[i][M][k];
for(i=1;i<=T;tmp2*=LTN[i],i++)
for(k=1;k<N;k++)
LTN[i]+=d[i][M][k];
printf("%.3lf\n",tmp1-tmp2);
}
return 0;
}附上discuss上一组数据：
10 20 10
0.1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.2
1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.8
0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.7
0.2 0.23 0.56 0.2 0.23 0.56 0.2 0.23 0.56 0.88
0.56 0.2 0.23 0.56 0.88 0.56 0.2 0.23 0.56 0.88
0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12 0.82 0.47
0.82 0.47 0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12
0.37 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82 0.47
0.472 0.373 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82
0.1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.2
1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.8
0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.7
0.2 0.23 0.56 0.2 0.23 0.56 0.2 0.23 0.56 0.88
0.56 0.2 0.23 0.56 0.88 0.56 0.2 0.23 0.56 0.88
0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12 0.82 0.47
0.82 0.47 0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12
0.37 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82 0.47
0.472 0.373 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82
0.56 0.88 0.56 0.2 0.23 0.373 0.99 0.12 0.82 0.472
0.472 0.373 0.99 0.12 0.82 0.82 0.472 0.373 0.99 0.33
结果：0.740
posted on 2009-07-19 17:13
wyiu 阅读(422)
评论(1) 编辑 收藏 引用 所属分类:
POJ