[閒聊] leetcode - 楓之谷衝裝

[yam276 (史萊哲林的優等生)]

題目：

你是一個楓之谷玩家，你想衝一個 +8 Atk 以上的工地手套

已知一個工地手套成本 50,000 可以衝 5 次

一張 手套攻擊卷軸 60% 成本 2,000,000 可以 +2 攻

一張 手套攻擊卷軸 10% 成本 1,000,000 可以 +3 攻

計算衝至少 +8 的工地手套需要多少期望成本


測資還會給你隨機的基底成本以及卷軸

要求你計算衝到目標數值的期望值


Description

You are enhancing a **weapon** using scrolls.
Each scroll has a **success probability**, **cost**, and **attack bonus** (if
successful).
You may apply **up to `max_scrolls` scrolls**, in a fixed order of your
choosing.

The weapon has a **base cost** (just for the raw item).
Your goal is to produce **one weapon** with **at least `target_attack` total
attack**.


Smart Strategy: Rational Stop-Loss

You are clever. If at any point it becomes **mathematically impossible** to
reach `target_attack` (even if all remaining scrolls succeed), you immediately
 stop and discard the weapon to avoid wasting more scrolls.
You pay the cost incurred so far, but not more.

Your job is to determine the **minimum expected total cost** (including
failure attempts) needed to **successfully create one such weapon**, using up
to `max_scrolls`.


Signature

```rust
pub fn min_expected_cost_to_target_attack(
    base_cost: u32,

    scrolls: Vec<(f64, u32, u32)>,
    // (success_probability, cost, attack_bonus)

    target_attack: u32,
    max_scrolls: usize,
) -> i64;
```


Return

Return the **minimum expected total cost**, in **gold coins**, **rounded down*
* to the nearest integer.
If it is **impossible** to reach `target_attack` even if all scrolls succeed,
return `-1`.


Constraints

* `1 <= base_cost <= 10^7`
* `1 <= scrolls.len() <= 10`
* Each `success_probability` ∈ `(0.0, 1.0)`
* Each `cost <= 10^7`
* Each `attack_bonus <= 10`
* `1 <= target_attack <= 50`
* `1 <= max_scrolls <= 10`


Tags

* `Dynamic Programming`
* `Probability`
* `Expected Value`
* `Recursion`
* `Memoization`

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1750667473.A.BF3.html
推 DaibaNana: 10%的現在要200喔
→ yam276: 100
→ walter741225: 要+8感覺要先用10%連過二
→ walter741225: 沒有就丟
→ walter741225: 剩下再開始用60%
→ walter741225: 因為現實就是 +8 只容許失敗一次
→ walter741225: 而10%要成功兩次 才能補足60%失敗一次
→ yam276: 要是我10%能連過2 對ㄚ
→ walter741225: 這社會是現實的 對ㄚ
→ yam276: 可是這題目又不是要你當天選之人==
→ walter741225: 只是覺得+8感覺不簡單
→ walter741225: 而且這10%真的也好貴 不太划算