ssworld VS DDD hdu 概率DP

前端之家收集整理的这篇文章主要介绍了ssworld VS DDD hdu 概率DP前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
#include <stdio.h>//注意题意,是从第一个人先胜的常熟的=第二个人的hp时,才赢.所以n和m应该反过来枚举
#include <cstring>
#define maxn 2001
double dp[maxn][maxn];
double a[6];
double b[6];


int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=1; i<=6; i++)
            scanf("%lf",&a[i]);
        for(int i=1; i<=6; i++)
            scanf("%lf",&b[i]);
        double aa=0,bb=0;
        //枚举所有的a>b的可能性用独立原理求每一次a,b胜出的概率
        for(int i=2; i<=6; i++)
            for(int j=1; j<i; j++)
            {
                aa+=a[i]*b[j];
                bb+=b[i]*a[j];
            }
        double p=1-aa-bb;
        if(p==1) aa=bb=0;
        else
        {
            aa=aa/(1-p);
            bb=bb/(1-p);
        }
        memset(dp,sizeof(dp));
        dp[0][0]=1;//该情况初始时必然发生
        for(int i=0; i<=m; i++)
            for(int j=0; j<=n; j++)
            {
                //dp[i][j]=aa*dp[i-1][j]+bb*dp[i][j-1];dp过程中要注意下标可能越界时要分裂处理,如下.
                if(i||j)
                {
                    dp[i][j]=0;
                    if(i)
                        dp[i][j]+=dp[i-1][j]*aa;
                    if(j)
                        dp[i][j]+=dp[i][j-1]*bb;
                }
            }
        double ans=0;
        for(int i=0; i<=n-1; i++)//i不能枚举到n.否则相平.
            ans+=dp[m-1][i]*aa;//m-1*aa是第m场.
        if(ans>1) ans=1;
        printf("%.6lf\n",ans);
    }
    return 0;
}

猜你在找的设计模式相关文章