Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

概率DP第一道

Posted by JohnSmith4096 at 2017-03-04 23:46:45 on Problem 2151
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator