hdu 3076 ssworld VS DDD (概率dp)

///题意：
/// A,B掷骰子，对于每一次点数大者胜，平为和，A先胜了m次A赢，B先胜了n次B赢。
///p1表示a赢，p2表示b赢，p=1-p1-p2表示平局
///a赢得概率 比一次p1 两次p0*p1 三次 p0^2*p1,即A赢的概率为p1+p*p1+p^2*p1+...p^n*p1,n->无穷
///即a_win=p1/(1-p);b_win=p2/(1-p);
///dp[i][j]表示a赢了j次，b赢了i次的概率
///dp[i][j]=dp[i-1][j]*b_win+dp[i][j-1]*a_win;
///ps:（两人的血量要换一换，数据错了）
# include <stdio.h>
# include <algorithm>
# include <iostream>
# include <string.h>
using namespace std;
double dp[2010][2010];
int main()
{
    int i,j,n,m;
    double p1,p2,p,a_win,b_win,a[10],b[10];
    while(~scanf("%d%d",&m,&n))
    {
        for(i=1; i<=6; i++)
            scanf("%lf",&a[i]);
        for(i=1; i<=6; i++)
            scanf("%lf",&b[i]);
        a_win=0;
        b_win=0;
        for(i=2; i<=6; i++)
        {
            for(j=1; j<i; j++)
            {
                a_win+=a[i]*b[j];
                b_win+=b[i]*a[j];
            }
        }
        p1=a_win;
        p2=b_win;
        p=1-p1-p2;
        if(p==1)
            printf("0.000000\n");//为平局，a不可能赢
        else
        {
            a_win=p1/(1-p);
            b_win=p2/(1-p);
        }
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(i=0; i<n; i++) //b赢得次数
        {
            for(j=0; j<m; j++) //a赢得次数
            {
                if(i==0&&j==0)
                    continue;
                dp[i][j]=0;
                if(j>0)
                    dp[i][j]+=dp[i][j-1]*a_win;
                if(i>0)
                    dp[i][j]+=dp[i-1][j]*b_win;
            }
        }
        double ans=0;
        for(i=0; i<n; i++)
            ans+=dp[i][m-1]*a_win;
        if(ans>1)
            ans=1;
        printf("%.6lf\n",ans);
    }
    return 0;
}

hdu 3076 ssworld VS DDD (概率dp)

原文：http://blog.csdn.net/lp_opai/article/details/39941101