//解釋轉(zhuǎn)的~~~~~~
『題目大意』
一次比賽中，共M道題，T個(gè)隊(duì)，p[i][j]表示隊(duì)i解出題j的概率；問每隊(duì)至少解出一題且
冠軍隊(duì)至少解出N道題的概率。
『算法』
設(shè)a[i][j][k]表示第i隊(duì)在前j道題中共解出k道題的概率，易得a[i][j][k]有如下遞推
關(guān)系(另需考慮邊界條件)：
a[i][j][k] = a[i][j-1][k-1] * p[i][j] + a[i][j-1][k] * (1-p[i][j])
設(shè)s[i][j]表示a[i][M][0] + a[i][M][1] + ... + a[i][M][j]
問題的解可以轉(zhuǎn)化為：每隊(duì)均至少做一題的概率（用P1表示）減去每隊(duì)做題數(shù)均在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])
『算法復(fù)雜度』
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]; //每隊(duì)至少做出一題的概率
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上一組數(shù)據(jù)：
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
結(jié)果：0.740
posted on 2009-07-19 17:13
wyiu 閱讀(464)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
POJ