楼主:
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`