//解釋轉的~~~~~~
『題目大意』
一次比賽中，共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 閱讀(448)
評論(1) 編輯 收藏 引用 所屬分類:
POJ