【POJ】【2151】Check the difficulty of problems

概率DP

　　一开始题目看错导致想转移方程想错了……想成f[i][j]表示前 i 个队伍中最多的做出来 j 道题的概率……sigh

　　看了下题解……其实是对于每个队伍 i 单独考虑做出来 j 道题的概率！！最后再根据情况将t个队伍合并起来……

WA：又忘了POJ上double输出应该用%f了……so sad

 1 //POJ 2151
 2 #include<cmath>
 3 #include<vector>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define rep(i,n) for(int i=0;i<n;++i)
10 #define F(i,j,n) for(int i=j;i<=n;++i)
11 #define D(i,j,n) for(int i=j;i>=n;--i)
12 #define pb push_back
13 using namespace std;
14 int getint(){
15     int v=0,sign=1; char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') sign=-1; ch=getchar();}
17     while(isdigit(ch))  {v=v*10+ch-'0'; ch=getchar();}
18     return v*sign;
19 }
20 const int N=1010,INF=~0u>>2;
21 /*******************template********************/
22 double p[N][35],f[N][31][31],s[N][31];
23 int main(){
24     int n,m,t;
25     while(scanf("%d%d%d",&m,&t,&n)!=EOF && m){
26         F(i,1,t) F(j,1,m) scanf("%lf",&p[i][j]);
27         
28         F(i,1,t){
29             f[i][0][0]=1.0;
30             F(j,1,m)
31                 f[i][j][0]=f[i][j-1][0]*(1-p[i][j]);
32             F(j,1,m) F(k,1,j)
33                 f[i][j][k]=f[i][j-1][k-1]*p[i][j]+f[i][j-1][k]*(1-p[i][j]);
34             s[i][0]=f[i][m][0];
35             F(k,1,m) s[i][k]=s[i][k-1]+f[i][m][k];
36         }
37         double p1=1,p2=1;
38         F(i,1,t){
39             p1*=(1-s[i][0]);
40             p2*=(s[i][n-1]-s[i][0]);
41         }
42         printf("%.3f
",p1-p2);
43     }
44     return 0;
45 }

View Code