作者:
yam276 ('_')
2025-06-23 16:31:11題目：
你是一個楓之谷玩家，你想衝一個 +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`