米哈游20230924秋招T2-米小游與魔法少女-奇運

題目描述與示例

題目描述

米小游都快保底了還沒抽到希兒，好生氣哦！只能打會活動再拿點水晶。

米小游和世界第一可愛的魔法少女 TeRiRi 正在打 BOSS，BOSS 的血量為h，當 BOSS 血量小于等于0時，BOSS 死亡。TeRiRi 有一套牌，在一輪中，她會按順序一張一張的將卡牌打出，套牌中有兩種卡牌：

1. 時來運轉：獲得x個幸運幣。
2. 幸運一擲：造成x點傷害，并投擲所有幸運幣，造成等于所有幸運幣擲出的點數(shù)之和的傷害。

幸運幣可以等概率的投擲出1～6之間的點數(shù)。 （所以為什么不叫骰子呢？）

米小游想知道，TeRiRi 的套牌在一輪內擊殺 BOSS 的概率。

輸入描述

第一行輸入兩個整數(shù)n (1≤n≤100)，h (1≤h≤10^9)，分別表示卡牌張數(shù)和 BOSS 血量。

接下來n行，每行首先輸入兩個整數(shù)t (1≤t≤2)，x (1≤x≤10)，t為1表示卡牌為時來運轉，t為2表示卡牌為幸運一擲。

輸出描述

輸出一個實數(shù)表示答案，你的答案與標準答案的誤差不超過10^?4都被認為是正確答案。

示例一

輸入

2 5
1 1
2 1

輸出

0.5

說明

幸運幣擲出4及以上的概率為0.5，再加上1點固定傷害，即可擊殺BOSS。

示例二

輸入

3 1145
1 4
1 9
1 9

輸出

0

說明

無論如何都無法擊殺BOSS。

解題思路

對于固定順序的套牌，投擲幸運幣的數(shù)量是固定的。這里要注意的是，由于時來運轉之后必須接上幸運一擲才能將幸運幣打出造成傷害，所以如果最后的若干張連續(xù)的卡牌是時來運轉，這些最后獲得的幸運幣也是無法造成傷害的。

我們將造成的傷害分為兩部分，固定傷害和隨機傷害，前者為打出y個幸運幣必定造成的z點傷害，后者為y個幸運幣擲出點數(shù)和的傷害。

假設整套卡牌一共投擲了y個幸運幣，造成的固定傷害為z點，如果想要擊殺BOSS，隨機傷害必須至少達到h-z點才可以。當然，如果h-z≤0，則必定可以擊殺BOSS。

問題就轉換為，投擲出y個幸運幣，點數(shù)總和超過h-z的概率是多少？

由于每一個幸運幣都是獨立的，在擲出第i個幸運幣時，其結果是從擲出第i-1個幸運幣時得到的各種結果轉移得到的，因此我們可以使用動態(tài)規(guī)劃來解決該問題。我們考慮動態(tài)規(guī)劃三部曲：

1. dp數(shù)組的含義是什么？

• dp數(shù)組是一個長度為(y+1)×(h-z+1)的二維矩陣，dp[i][j]表示擲出第i個幸運幣時，有多大的概率可以取得和為j的結果，即造成和為j的傷害。
• 特別地，由于只需要判斷傷害之和大于等于h-z的概率，而不用關心具體的分布，dp數(shù)組內層的第h-z個元素，即dp[i][h-z]，表示求和大于等于h-z的概率。

2. 動態(tài)轉移方程是什么？

• 由于幸運幣擲出點數(shù)1-6是等概率的，故對于某一個特定的dp[i-1][j]，在擲出第i個幸運幣時，dp[i-1][j]的結果將等概率地轉換到dp[i][j+1]，dp[i][j+2]，dp[i][j+3]，dp[i][j+4]，dp[i][j+5]，dp[i][j+6]，即每一個狀態(tài)都可以取得1/6的轉移。
• 另外，如果j+k之后超過了h-z，則將直接獲得(7-k)/6 * dp[i-1][j]的概率。

for i in range(1, y+1):for j in range(i-1, h-z+1):for k in range(1, 7):if j + k >= h - z:dp[i][h-z] += (7-k)/6 * dp[i-1][j]breakelse:dp[i][j+k] += 1/6 * dp[i-1][j]

3. dp數(shù)組如何初始化？

• 考慮不投擲任何幸運幣的情況，那么只有一種情況，也就是在投擲0個幸運幣的時候獲得求和為0的概率為恒定1。故初始化dp[0][0] = 1

dp = [[0] * (h-z+1) for _ in range(y+1)]
dp[0][0] = 1

考慮完上述問題后，代碼其實呼之欲出了。

代碼

Python

# 題目：【DP】米哈游2023秋招-米小游與魔法少女-奇運
# 作者：閉著眼睛學數(shù)理化
# 算法：DP
# 代碼有看不懂的地方請直接在群上提問y = 0       # 擲出幸運幣的總個數(shù)
z = 0       # 全部造成的固定傷害
x_temp = 0  # 時來運轉獲得的幸運幣n, h = map(int, input().split())
for _ in range(n):t, x = map(int, input().split())# 時來運轉if t == 1:x_temp += x# 幸運一擲else:y += x_tempx_temp = 0z += x# 如果固定傷害已經大于h，直接輸出1
if h - z <= 0:print(1)
# 否則才需要進行dp過程
else:# 初始化dp數(shù)組# dp[i][j]表示擲出了i個幸運幣時，# 有多大的概率可以取得和為j的結果，即造成和為j的傷害。dp = [[0] * (h-z+1) for _ in range(y+1)]dp[0][0] = 1# 考慮每一個幸運幣for i in range(1, y+1):# 對于每一個幸運幣考慮打出i-1個硬幣后的# 每一種求和結果的概率# 注意，由于已經擲出了i-1個幸運幣# 那么求和結果至少為i-1，因為每個幸運幣點數(shù)至少為1點# 因此j遍歷時起點可以從i-1開始for j in range(i-1, h-z+1):# 如果求和j尚未在上一次投擲中取得，# 則可以直接考慮下一個幸運幣if dp[i-1][j] == 0:break# 遍歷擲出六種不同點數(shù)k的情況，# 當前點數(shù)則可以取得j+kfor k in range(1, 7):# 如果當前點數(shù)j+k超過了擊殺所需點數(shù)# 則更新dp[i][h-z]# 為dp[i-1][j]對應的概率乘以(7-k)/6if j + k >= h - z:dp[i][h-z] += (7-k)/6 * dp[i-1][j]break# 如果當前點數(shù)j+k尚未超過擊殺所需點數(shù)# 則其概率由dp[i-1][j]六等分后轉移得到else:dp[i][j+k] += 1/6 * dp[i-1][j]# 輸出最后一行的最后一個元素# 表示打出第y個幸運幣后，造成傷害大于等于h-z點的概率print(dp[y][h-z])

Java

import java.util.Scanner;public class Main {public static void main(String[] args) {int y = 0;            // 擲出幸運幣的總個數(shù)int z = 0;            // 全部造成的固定傷害int x_temp = 0;       // 時來運轉獲得的幸運幣Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int h = scanner.nextInt();for (int i = 0; i < n; i++) {int t = scanner.nextInt();int x = scanner.nextInt();// 時來運轉if (t == 1) {x_temp += x;}// 幸運一擲else {y += x_temp;x_temp = 0;z += x;}}// 如果固定傷害已經大于h，直接輸出1if (h - z < 0) {System.out.println("1");}// 否則才需要進行dp過程else {// 初始化dp數(shù)組// dp[i][j]表示擲出了i個幸運幣時，// 有多大的概率可以取得和為j的結果，即造成和為j的傷害。double[][] dp = new double[y + 1][h - z + 1];dp[0][0] = 1.0;// 考慮每一個幸運幣for (int i = 1; i <= y; i++) {// 對于每一個幸運幣考慮打出i-1個硬幣后的// 每一種求和結果的概率// 注意，由于已經擲出了i-1個幸運幣// 那么求和結果至少為i-1，因為每個幸運幣點數(shù)至少為1點// 因此j遍歷時起點可以從i-1開始for (int j = i - 1; j <= h - z; j++) {// 如果求和j尚未在上一次投擲中取得，// 則可以直接考慮下一個幸運幣if (dp[i - 1][j] == 0) {break;}// 遍歷擲出六種不同點數(shù)k的情況，// 當前點數(shù)則可以取得j+kfor (int k = 1; k <= 6; k++) {// 如果當前點數(shù)j+k超過了擊殺所需點數(shù)// 則更新dp[i][h-z]// 為dp[i-1][j]對應的概率乘以(7-k)/6if (j + k >= h - z) {dp[i][h - z] += (7 - k) / 6.0 * dp[i - 1][j];break;}// 如果當前點數(shù)j+k尚未超過擊殺所需點數(shù)// 則其概率由dp[i-1][j]六等分后轉移得到else {dp[i][j + k] += 1.0 / 6.0 * dp[i - 1][j];}}}}// 輸出最后一行的最后一個元素// 表示打出第n個幸運幣后，造成傷害大于等于h-z點的概率System.out.println(String.format("%.5f", dp[y][h - z]));}}
}

C++

#include <iostream>
#include <vector>
#include <iomanip>using namespace std;int main() {int y = 0;            // 擲出幸運幣的總個數(shù)int z = 0;            // 全部造成的固定傷害int x_temp = 0;       // 時來運轉獲得的幸運幣int n, h;cin >> n >> h;for (int i = 0; i < n; i++) {int t, x;cin >> t >> x;// 時來運轉if (t == 1) {x_temp += x;}// 幸運一擲else {y += x_temp;x_temp = 0;z += x;}}// 如果固定傷害已經大于h，直接輸出1if (h - z < 0) {cout << fixed << setprecision(10) << 1 << endl;}// 否則才需要進行dp過程else {// 初始化dp數(shù)組// dp[i][j]表示擲出了i個幸運幣時，// 有多大的概率可以取得和為j的結果，即造成和為j的傷害。vector<vector<double>> dp(y + 1, vector<double>(h - z + 1, 0));dp[0][0] = 1.0;// 考慮每一個幸運幣for (int i = 1; i <= y; i++) {// 對于每一個幸運幣考慮打出i-1個硬幣后的// 每一種求和結果的概率// 注意，由于已經擲出了i-1個幸運幣// 那么求和結果至少為i-1，因為每個幸運幣點數(shù)至少為1點// 因此j遍歷時起點可以從i-1開始for (int j = i - 1; j <= h - z; j++) {// 如果求和j尚未在上一次投擲中取得，// 則可以直接考慮下一個幸運幣if (dp[i - 1][j] == 0) {break;}// 遍歷擲出六種不同點數(shù)k的情況，// 當前點數(shù)則可以取得j+kfor (int k = 1; k <= 6; k++) {// 如果當前點數(shù)j+k超過了擊殺所需點數(shù)// 則更新dp[i][h-z]// 為dp[i-1][j]對應的概率乘以(7-k)/6if (j + k >= h - z) {dp[i][h - z] += (7 - k) / 6.0 * dp[i - 1][j];break;}// 如果當前點數(shù)j+k尚未超過擊殺所需點數(shù)// 則其概率由dp[i-1][j]六等分后轉移得到else {dp[i][j + k] += 1.0 / 6.0 * dp[i - 1][j];}}}}// 輸出最后一行的最后一個元素// 表示打出第n個幸運幣后，造成傷害大于等于h-z點的概率cout << fixed << setprecision(5) << dp[y][h - z] << endl;}return 0;
}

時空復雜度

時間復雜度：O(yh)。其中y為投擲出的幸運幣的總數(shù)，h為BOSS總血量，dp過程需要進行雙重循環(huán)。

空間復雜度：O(yh)。dp數(shù)組所占空間。如果使用滾動dp，空間復雜度可以降低到O(h)

---

華為OD算法/大廠面試高頻題算法練習沖刺訓練

• 華為OD算法/大廠面試高頻題算法沖刺訓練目前開始常態(tài)化報名！目前已服務100+同學成功上岸！

• 課程講師為全網(wǎng)50w+粉絲編程博主@吳師兄學算法 以及小紅書頭部編程博主@閉著眼睛學數(shù)理化

• 每期人數(shù)維持在20人內，保證能夠最大限度地滿足到每一個同學的需求，達到和1v1同樣的學習效果！

• 60+天陪伴式學習，40+直播課時，300+動畫圖解視頻，300+LeetCode經典題，200+華為OD真題/大廠真題，還有簡歷修改、模擬面試、專屬HR對接將為你解鎖

• 可上全網(wǎng)獨家的歐弟OJ系統(tǒng)練習華子OD、大廠真題

• 可查看鏈接 OD算法沖刺訓練課程表 & OD真題匯總(持續(xù)更新)

• 綠色聊天軟件戳 od1336了解更多