题目描述

题面

题目大意：两个人A、B，血量分别为HA、HB，轮流掷骰子，每个人掷骰子的6种情况都有一定的概率，谁点数小谁扣一滴血，没血了就输了，问A赢的概率。

坑点：血量输入是反的，而且听说总概率还可能不等于1。-_-||

题解

dp[i][j]表示A有i血，B有j血A赢的概率。概率正推，dp[x][0]=1.0(x!=0)，然后dp[i][j]=dp[i][j-1]*p1+dp[i-1][j]*p2，其中p1为每次A赢的概率，p2位每次B赢的概率。

注意平局不贡献答案，我们要预先处理出正确的p1和p2，忽略平局的影响。（说个类比，就是生物上的某基因型致死然后问你某个生物是某个基因型的概率）

然后由于double有爆空间的风险，直接滚动第一维即可。但是我想到一个问题，这样赋初值时让dp[0][0]=dp[1][0]=1.0，当i和j都为0时的状态的值不就错了吗？但是我们枚举状态时根本不会去算i=0或j=0的情况，所以根本没有这个转移，总之zenzen没问题。

代码

#include <iostream>@H_403_26@
#include <algorithm>@H_403_26@
#include <cstring>@H_403_26@
#include <cstdio>@H_403_26@
#include <cstdlib>@H_403_26@
#include <cmath>@H_403_26@

using@H_403_26@ namespace@H_403_26@ std@H_403_26@;

int@H_403_26@ n,m;
double@H_403_26@ dp[2@H_403_26@][2002@H_403_26@],a[7@H_403_26@],b[7@H_403_26@];

int@H_403_26@ main(){

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

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

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

        double@H_403_26@ p1 = 0.0@H_403_26@,p2 = 0.0@H_403_26@,sum;

        for@H_403_26@(int@H_403_26@ i = 0@H_403_26@; i <= m; i++)
            dp[0@H_403_26@][i] = dp[1@H_403_26@][i] = 0.0@H_403_26@;

        for@H_403_26@(int@H_403_26@ i = 1@H_403_26@; i <= 6@H_403_26@; i++)
            for@H_403_26@(int@H_403_26@ j = 1@H_403_26@; j <= 6@H_403_26@; j++){
                if@H_403_26@(i > j)  p1 += a[i] * b[j];
                if@H_403_26@(i < j)  p2 += a[i] * b[j];
            }

        sum = p1 + p2;
        p1 /= sum;
        p2 /= sum;

        int@H_403_26@ x = 0@H_403_26@;
        dp[0@H_403_26@][0@H_403_26@] = dp[1@H_403_26@][0@H_403_26@] = 1.0@H_403_26@;

        for@H_403_26@(int@H_403_26@ i = 1@H_403_26@; i <= n; i++){
            x ^= 1@H_403_26@;
            for@H_403_26@(int@H_403_26@ j = 1@H_403_26@; j <= m; j++)
            dp[x][j] = dp[x][j-1@H_403_26@] * p1 + dp[x^1@H_403_26@][j] * p2;
        }

        printf@H_403_26@("%.6lf\n"@H_403_26@,dp[x][m]);
    }

    return@H_403_26@ 0@H_403_26@;
}