米哈游20230924秋招T2-米小游與魔法少女-奇運(yùn)

題目描述與示例

題目描述

米小游都快保底了還沒(méi)抽到希兒，好生氣哦！只能打會(huì)活動(dòng)再拿點(diǎn)水晶。

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

1. 時(shí)來(lái)運(yùn)轉(zhuǎn)：獲得x個(gè)幸運(yùn)幣。
2. 幸運(yùn)一擲：造成x點(diǎn)傷害，并投擲所有幸運(yùn)幣，造成等于所有幸運(yùn)幣擲出的點(diǎn)數(shù)之和的傷害。

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

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

輸入描述

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

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

輸出描述

輸出一個(gè)實(shí)數(shù)表示答案，你的答案與標(biāo)準(zhǔn)答案的誤差不超過(guò)10^?4都被認(rèn)為是正確答案。

示例一

輸入

2 5
1 1
2 1

輸出

0.5

說(shuō)明

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

示例二

輸入

3 1145
1 4
1 9
1 9

輸出

0

說(shuō)明

無(wú)論如何都無(wú)法擊殺BOSS。

解題思路

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

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

假設(shè)整套卡牌一共投擲了y個(gè)幸運(yùn)幣，造成的固定傷害為z點(diǎn)，如果想要擊殺BOSS，隨機(jī)傷害必須至少達(dá)到h-z點(diǎn)才可以。當(dāng)然，如果h-z≤0，則必定可以擊殺BOSS。

問(wèn)題就轉(zhuǎn)換為，投擲出y個(gè)幸運(yùn)幣，點(diǎn)數(shù)總和超過(guò)h-z的概率是多少？

由于每一個(gè)幸運(yùn)幣都是獨(dú)立的，在擲出第i個(gè)幸運(yùn)幣時(shí)，其結(jié)果是從擲出第i-1個(gè)幸運(yùn)幣時(shí)得到的各種結(jié)果轉(zhuǎn)移得到的，因此我們可以使用動(dòng)態(tài)規(guī)劃來(lái)解決該問(wèn)題。我們考慮動(dòng)態(tài)規(guī)劃三部曲：

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

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

2. 動(dòng)態(tài)轉(zhuǎn)移方程是什么？

• 由于幸運(yùn)幣擲出點(diǎn)數(shù)1-6是等概率的，故對(duì)于某一個(gè)特定的dp[i-1][j]，在擲出第i個(gè)幸運(yùn)幣時(shí)，dp[i-1][j]的結(jié)果將等概率地轉(zhuǎn)換到dp[i][j+1]，dp[i][j+2]，dp[i][j+3]，dp[i][j+4]，dp[i][j+5]，dp[i][j+6]，即每一個(gè)狀態(tài)都可以取得1/6的轉(zhuǎn)移。
• 另外，如果j+k之后超過(guò)了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ù)組如何初始化？

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

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

考慮完上述問(wèn)題后，代碼其實(shí)呼之欲出了。

代碼

Python

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

Java

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

時(shí)空復(fù)雜度

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

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

---

華為OD算法/大廠面試高頻題算法練習(xí)沖刺訓(xùn)練

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

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

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

• 60+天陪伴式學(xué)習(xí)，40+直播課時(shí)，300+動(dòng)畫(huà)圖解視頻，300+LeetCode經(jīng)典題，200+華為OD真題/大廠真題，還有簡(jiǎn)歷修改、模擬面試、專(zhuān)屬HR對(duì)接將為你解鎖

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

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

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