思路：期望DP

定义$f[i][j]$为投掷前$i$次骰子，总和为$j$的概率

其中，初始化状态$f[0][0]=1.0$

状态转移方程为$f[i][j]=\sum_{k=1}^{a[i]}f[i-1][j-k]$

分别计算二者投掷前$i$次骰子，总和为$j$的概率，分别记为$f[i][j_1],g[i][j_2]$

赛诺获胜则有$j_1>j_2$

枚举计算即可

时间复杂度

$O(nm)$

代码

C++

#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
typedef long long ll;
typedef unsigned long long ull;
const int N=25,M=170;
int n,m,a[N],b[N];
double f[N][M],g[N][M];  //前i次掷骰子 总和为j的概率


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    f[0][0]=g[0][0]=1.0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=160;j++)
        {
            for(int k=j-1;k>=j-a[i]&&k>=0;k--)   
            {
                f[i][j]+=f[i-1][k]*1.0/a[i];
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=i;j<=160;j++)
        {
            for(int k=j-1;k>=j-b[i]&&k>=0;k--)
            {
                g[i][j]+=g[i-1][k]*1.0/b[i];
            }
        }
    }
    double res=0,pre=0;
    for(int i=2;i<=160;i++)
    {
        pre+=g[m][i-1];  //顺序遍历 不需要使用前缀和 直接统计
        res+=f[n][i]*pre;
    }
    printf("%.3f\n",res);
    return 0;
}

python代码

import sys
input=lambda:sys.stdin.readline()
write=lambda x:sys.stdout.write(str(x)+'\n')

n, m = list(map(int, input().split()))
nums1 = list(map(int, input().split()))
nums1 = [0] + nums1

nums2 = list(map(int, input().split()))
nums2 = [0] + nums2
dp1 = [[0] * (170) for _ in range(n + 1)]
dp2 = [[0] * (170) for _ in range(m + 1)]
dp1[0][0] = 1
dp2[0][0] = 1

for i in range(1, n + 1):
    for j in range(i, 160 + 1):
        for k in range(j-1, -1, -1):
            if k < j - nums1[i]:
                continue
            dp1[i][j] += dp1[i-1][k] * (1.0 / nums1[i])

for i in range(1, m + 1):
    for j in range(i, 160 + 1):
        for k in range(j-1, -1, -1):
            if k < j - nums2[i]:
                continue
            dp2[i][j] += dp2[i-1][k] * (1.0 / nums2[i])

res = 0
pre = 0
for i in range(2, 160):
    pre += dp2[m][i-1]
    res += dp1[n][i] * pre



print("%.3f" % res)

Java代码

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] a = new int[n], b = new int[m];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
        double[][] dp1 = new double[n+1][161];
        dp1[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 161; j++) {
                for (int k = 1; k <= a[i] && j+k < 161; k++) {
                    dp1[i+1][j+k] += dp1[i][j] / a[i];
                }
            }
        }
        double[][] dp2 = new double[m+1][161];
        dp2[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 161; j++) {
                for (int k = 1; k <= b[i] && j+k < 161; k++) {
                    dp2[i+1][j+k] += dp2[i][j] / b[i];
                }
            }
        }
        double ans = 0;
        for (int i = 0; i < 161; i++) {
            for (int j = i+1; j < 161; j++) {
                ans += dp1[n][j] * dp2[m][i];
            }
        }
        System.out.printf("%.3f\n", ans);
    }
}

题目内容

赛诺与提纳里每天都要来一把七圣召唤，但是最近赛诺的骰子太差了，总是用不出技能，然后输给骰子很好的小提。于是赛诺放弃了打牌，决心要用骰子来与提纳里一决胜负。提纳里便找来妙论派的前辈做出特制的骰子用来和赛诺对决。每个特制骰子有固定的面数 $k\ (2\leqslant k\leqslant 8)$，每一面对应的点数分别为 $1,2,\dots,k$。

赛诺有 $n\ (1\leqslant n\leqslant 20)$ 个骰子，对于骰子 $i\ (1\leqslant i\leqslant n)$，它的面数为 $a_i\ (2\leqslant a_i\leqslant 8)$，摇到每一面的概率都是 $\frac{1}{a_i}$。提纳里有 $m\ (1\leqslant m\leqslant 20)\$个骰子，对于骰子 $j\ (1\leqslant j\leqslant m)$，它的面数为 $b_j\ (2\leqslant b_j\leqslant 8)$，摇到每一面的概率都是 $\frac{1}{b_i}$。

赛诺和提纳里分别摇各自拥有的全部骰子，然后把骰子朝上那一面的点数相加，最后比较谁的点数和最大，大的获胜，相同平手，小的获败。赛诺和提纳里只摇一把，平手不会继续重摇，赛诺想知道他获胜的概率，你能帮帮他吗？

输入描述

共三行，第一行包含两个正整数 $n$ 和 $m$ ，

第二行包含 $n$ 个整数，表示 $a_0,a_1,\dots,a_{n-1}$，

第三行包含 $m$ 个整数，表示 $b_0,b_1,\dots , b_{m-1}$。

输出描述

共一行，一个浮点数，表示赛诺获胜的概率，保留小数点后3位有效数字。

样例

输入

1 3
8
2 3 4

输出

0.255	

说明

100%的数据：$1\leqslant n,m\leqslant 20,\ 2\leqslant a_i,b_i\leqslant 8$。