hdu3076—概率dp

标签 ： 概率dp

---

题目链接

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 2008;

double dp[N][N];//dp[i][j]表示的是第一个人有i血，第二个人有j个血的时候1赢的概率。

double a[6],b[6];

int main()

{

    int n, m;

    while(~scanf("%d%d",&m,&n))

    {

        for(int i = 0; i < 6; i++)  scanf("%lf",&a[i]);

        for(int j = 0; j < 6; j++)  scanf("%lf",&b[j]);

        double p1, p2, ping;

        p1 = p2 = ping = 0;

        for(int i = 0; i < 6; i++){

            for(int j = 0; j <= 6; j++){

                //if(i==j) ping += a[i]*b[j];

                if(i>j)

                    p1 += a[i]*b[j];

                else if(i<j)

                    p2 +=a[i]*b[j];

            }

        }

       // p2 = 1-p1-ping;

        double tm = p1+p2;

        p1 = p1/tm;

        p2 = p2/tm;

        //printf("%lf %lf %lf\n",p1,p2,ping);

        for(int i = 0; i <= m; i++) dp[0][i] = 0;

        for(int j = 0; j <= n; j++) dp[j][0] = 1;

        for(int i = 1; i <= n; i++){

            for(int j = 1; j <= m; j++){

                dp[i][j] = dp[i-1][j]*p2+dp[i][j-1]*p1;

            }

        }

        printf("%lf\n",dp[n][m]);

    }

    return 0;

}

/*

//下面是错误的代码，因为想一下其实每次得到的不是最后的解，那么精度会有很大问题

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 2008;

double dp[N][N];//dp[i][j]表示第一个人失去i格血，第二个人失去j格血的时候1赢的概率；

double a[6],b[6];

int main()

{

    int n,m;

    while(~scanf("%d%d",&n,&m))

    {

        for(int i = 0; i < 6; i++) scanf("%lf",&a[i]);

        for(int i = 0; i < 6; i++) scanf("%lf",&b[i]);

        double p = 0;

        double p2 = 0;

        double ping = 0;

        for(int i = 0; i < 6; i++){

            for(int j = 0; j < i; j++){

                if(i==j) ping = a[i]*b[j];

                else

                    p += a[i]*b[j];

            }

        }

        p2 = 1-p-ping;

      //  printf("%lf %lf\n",p,p2);

       // memset(dp,0,sizeof(dp));

       for(int i = 0;i <= n; i++){

            for(int j = 0; j <= m; j++)

                dp[i][j] = 1;

       }

        dp[0][1] = p;

        dp[1][0] = p2;

        for(int i = 1; i <= n; i++){

            for(int j = 1; j <= m; j++){

                dp[i][j] = dp[i-1][j]*p2+dp[i][j-1]*p;

            }

        }

        double ans = 0;

        for(int i = 0; i < n; i++){

            ans*=dp[i][m];

        }

        printf("%lf\n",ans);

    }

    return 0;

}

*/