| ||||||||||
| 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