Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
概率DP第一道#include <cstdio> #include <cstring> using namespace std; const int maxm=35,maxt=1010,maxn=maxm; int m,t,n; double a[maxt][maxm]; double x[2][maxm]; double dp; void solve() { double p1=1,p2=1; for(int i=1;i<=t;i++) { double tmp=1; for(int j=1;j<=m;j++) tmp*=(1-a[i][j]); tmp=1.0-tmp; p1*=tmp; } for(int i=1;i<=t;i++) { int index=0; memset(x,0,sizeof(x)); //滚动数组清零 x[0][0]=1; for(int j=1;j<=m;j++) { index^=1; x[index][0]=x[index^1][0]*(1-a[i][j]); for(int k=1;k<=j;k++) x[index][k]=x[index^1][k]*(1-a[i][j])+x[index^1][k-1]*a[i][j]; } dp=0; for(int j=1;j<=n-1;j++) dp+=x[index][j]; p2*=dp; } printf("%.3f\n",p1-p2); } int main() { while(~scanf("%d%d%d",&m,&t,&n)&&(m!=0||t!=0||n!=0)) { for(int i=1;i<=t;i++) for(int j=1;j<=m;j++) scanf("%lf",&a[i][j]); solve(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator