| 题目名称 | 3710. 西班牙寻宝 |
|---|---|
| 输入输出 | huntinspain.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 lihaoze
于2022-07-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：0， 提交：0， 通过率：0% | |||
| 关于 西班牙寻宝 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
本来是为了暑期训练比赛准备的题，还把题解写好了，但是无奈因为疫情原因取消了
 ，就直接把题解放出来吧 西班牙寻宝 （我觉得我写的 latex beamer 还是蛮标准的，用的模板是 THU-Beamer-Theme ，还在用ppt写公式的神犇可以学习一下） lihaoze
2022-08-03 10:09
1楼
| ||||
【题目描述】
无数的宝藏被埋藏在西班牙的 $n$ 个随机地点。对于每一个地点，你都知道挖到宝藏的概率 $p_i$，和挖该宝藏消耗的体力 $c_i$。请你找到一个挖宝顺序，使得挖到第一个宝藏平均所需的总体力最少。
假如我们有一个挖宝顺序 $(a, b)$，那么对于挖到第一个宝藏是 $a$ 和 $b$，所需的总体力为 $\mathrm{c}(a) + (1 - \mathrm{p}(a)) \times \mathrm{c}(b)$。
【输入格式】
第一行，包括一个正整数 $n$，表示藏宝地点的数量。 接下来 $n$ 行，每行分别有一个双精度浮点数和一个正整数，分别用 $p_i$ 和 $c_i$ 表示。
【输出格式】
输出一行一个正整数(向下取整)，表示挖到第一个宝藏所需的最少平均总体力。
【样例输入】
10 0.324 33 0.497 100 0.965 58 0.168 61 0.363 32 0.487 9 0.392 24 0.368 15 0.105 69 0.675 92
【样例输出】
3
【数据规模与约定】
对于 $100 \%$ 的数据，$1 \leq n \leq 500$, $0 \le p_i \le 1$, $1 \leq c_i \leq 1000000$。
【来源】
Simon H A, Kadane J B. Optimal problem-solving search: All-or-none solutions[J]. Artificial Intelligence, 1975, 6(3): 235-247.