学步园

ZZ tp://www.cppblog.com/proyao/archive/2009/07/19/90527.aspx

『题目大意』
一次比赛中，共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)

#include <iostream><br /> #include <cstring><br /> #include <cstdio><br /> using namespace std;<br /> double dp[32][32];<br /> double p[32];<br /> double p1=1,p2=1;<br /> void dp_pro(int m,int n)<br /> {<br /> //dp[i][j]表示当前team对前i道题目能作对j道的概率<br /> //dp[i][j] = dp[i-1][j]*(1-p[i]) + dp[i-1][j-1]*p[i]</p> <p> int i = 0;<br /> int j =0;<br /> dp[0][0]=1.0;<br /> double sum[32]={1.0};<br /> for(i=1;i<=m;i++)<br /> {<br /> sum[i]=1.0;<br /> for(j=1;j<=i;j++)<br /> sum[i] *= (1-p[j]);<br /> }<br /> for(i=1;i<=m;i++)<br /> dp[i][0]= sum[i];<br /> for(i=1;i<=m;i++)<br /> for(j=1;j<=i;j++)<br /> {<br /> dp[i][j] = dp[i-1][j]*(1-p[i]) + dp[i-1][j-1]*p[i];<br /> // printf("dp[%d][%d] = %.3f/n",i,j,dp[i][j]);<br /> }<br /> for(i=0;i<=m;i++)<br /> {<br /> sum[i]=0;<br /> for(j=0;j<=i;j++)<br /> sum[i] +=dp[m][j];<br /> }<br /> p1*=sum[m]-sum[0];//当前队至少做一道题的概率<br /> p2*=sum[n-1]-sum[0];//做1～n-1道题的概率<br /> //cout<<p1<<" "<<p2<<endl;<br /> }<br /> int main()<br /> {<br /> int m,t,n;<br /> cin>>m;<br /> cin>>t;<br /> cin>>n;<br /> int i = 0;<br /> int j = 0;<br /> while(m || t || n)<br /> {<br /> memset(dp,0,sizeof(dp));<br /> memset(p,0,sizeof(p));<br /> p1=1.0;<br /> p2=1.0;<br /> for(i=1;i<=t;i++)<br /> {<br /> for(j=1;j<=m;j++)<br /> cin>>p[j];<br /> dp_pro(m,n);<br /> }<br /> printf("%.3f/n",p1-p2);<br /> //p1-p2就是在每个队至少作对一道题的情况下除去每个队都做了（1~n-1）道题的补集。<br /> //即为至少有一个对做了n-1道题<br /> cin>>m;<br /> cin>>t;<br /> cin>>n;<br /> }<br /> }