题解：期望DP

这里有一个细节就是，需要使用第二种卡牌的时候，收集到的硬币才会被打出，因此需要记录打出的硬币数，然后并把怪物的血量扣除固定值$x$的伤害

定义$f[i][j]$为投掷前$i$次 点数总和为$j$的概率

最终首先判断投掷的次数$num*6$是否小于$h$

不小于的话，就把对应的概率之和累加

$f[i][j]=\sum_{k = j-6}^{k = j-1} f[i-1][k]$

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010,M=6010;
int n,t,h,x;
double f[N][M];  //投掷前i次 点数总和为j的概率
int main() {
    int cnt=0,num=0;  //硬币数量
    cin>>n>>h;
    for(int i=0;i<n;i++){
        cin>>t>>x;
        if(t==1){
            cnt+=x;
        }
        else{
            h-=x;
            num+=cnt;
            cnt=0;
        }
    }
    f[0][0]=1.0;
    for(int i=1;i<=num;i++){
        for(int j=i;j<=num*6;j++){
            for(int k=1;k<=6;k++){
                if(j>=k){
                    f[i][j]+=f[i-1][j-k]*1.0/6;
                }
            }
        }
    }
    double res=0.0;
    if(h<=num*6){
        for(int i=h;i<=num*6;i++){
            res+=f[num][i];
        }
    }
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    static final int N = 1010;
    static final int M = 6010;
    static int n, t, h, x;
    static double[][] f = new double[N][M];  // 投掷前 i 次，点数总和为 j 的概率

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = 0, num = 0;  // 硬币数量
        n = sc.nextInt();
        h = sc.nextInt();
        for (int i = 0; i < n; i++) {
            t = sc.nextInt();
            x = sc.nextInt();
            if (t == 1) {
                cnt += x;
            } else {
                h -= x;
                num += cnt;
                cnt = 0;
            }
        }
        f[0][0] = 1.0;
        for (int i = 1; i <= num; i++) {
            for (int j = i; j <= num * 6; j++) {
                for (int k = 1; k <= 6; k++) {
                    if (j >= k) {
                        f[i][j] += f[i - 1][j - k] * 1.0 / 6;
                    }
                }
            }
        }
        double res = 0.0;
        if (h <= num * 6) {
            for (int i = h; i <= num * 6; i++) {
                res += f[num][i];
            }
        }
        System.out.printf("%.4f\n", res);
    }
}

Python

N = 1010
M = 6010
f = [[0.0 for _ in range(M)] for _ in range(N)]  # 投掷前 i 次，点数总和为 j 的概率

n, h = map(int, input().split())
cnt = num = 0  # 硬币数量
for _ in range(n):
    t, x = map(int, input().split())
    if t == 1:
        cnt += x
    else:
        h -= x
        num += cnt
        cnt = 0
f[0][0] = 1.0
for i in range(1, num + 1):
    for j in range(i, num * 6 + 1):
        for k in range(1, 7):
            if j >= k:
                f[i][j] += f[i - 1][j - k] * 1.0 / 6
res = 0.0
if h <= num * 6:
    for i in range(h, num * 6 + 1):
        res += f[num][i]
print("%.4f" % res)

题目描述

米小游正在打$BOSS$，当$BOSS$血量小于等于0时，$BOSS$死亡。米小游的血量为$h$，有一套牌，在一轮中，她会按顺序一张一张的将卡牌打出，套牌中有两种卡牌:

1.德玛西亚之力：获得$x$个幸运币

2.大威天龙：造成$x$点伤害，并投掷所有幸运币，造成等于所有幸运币掷出的点数之和的伤害

幸运币可以等概率的投掷出1~6之间的点数。米小游想知道，他的一套牌在一轮内击杀BOSS的概率

输入格式

第一行输入两个整数$n(1< n <100),h(1< h <10^9)$，分别表示卡牌张数和BOSS血量。 接下来$n$行每行首先输入两个整数$t(1\le t\le 2),x(1\le x\le 10)$，$t$为1表示卡牌为德玛西亚之力，$t$为2表示卡牌为大威天龙。

输出格式

输出一个实数表示答案，仅输出小数点后4位

样例

输入

2 5
1 1
2 1

输出

0.5000

说明

幸运币掷出4及以上的概率为0.5，再加上1点固定伤害，即可击杀BOSS。