前端之家收集整理的这篇文章主要介绍了
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;
}