题目详情题解（0）讨论（0）提交记录（0）

AT_abc402_e.[ABC402E] Payment Required

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 30XX 年，某场比赛中每次提交都需要支付费用。

这场比赛共有 NN 道题目。第 ii 道题目的分值为 SiS_i 分，每次提交需要支付 CiC_i 日元。

高桥君在第 ii 道题目上提交时，有 Pi%P_i\% 的概率能正确解答该题。每次提交能否正确解答与之前的提交结果相互独立。

高桥君当前拥有 XX 日元。提交所花费的总金额不能超过 XX 日元。

请计算在高桥君采取最优提交策略的情况下，他最终获得的总分的期望值最大值。

注意：

  • 高桥君可以根据之前的提交结果决定下一次提交哪道题目
  • 同一道题目即使多次正确解答，得分也不会重复计算

输入格式

输入通过标准输入给出，格式如下：

NN XX
S1S_1 C1C_1 P1P_1
S2S_2 C2C_2 P2P_2
⋮\vdots
SNS_N CNC_N PNP_N

输出格式

输出答案。当输出值与真实值的绝对误差或相对误差不超过 10−610^{-6} 时，将被判定为正确。

输入输出样例

  • 输入#1

    3 2
100 1 50
200 1 20
1000 1 1

    输出#1

    95

  • 输入#2

    2 7
100 3 50
100 2 50

    输出#2

    125

  • 输入#3

    5 32
500 9 57
300 4 8
300 3 32
300 7 99
100 8 69

    输出#3

    953.976967020096

  • 输入#4

    7 78
100 1 100
200 2 90
300 3 80
400 4 60
450 5 50
525 6 30
650 7 1

    输出#4

    1976.2441416041121021

说明/提示

约束条件

  • 1≤N≤81 \leq N \leq 8
  • 1≤Si≤27181 \leq S_i \leq 2718
  • 1≤Ci≤X≤50001 \leq C_i \leq X \leq 5000
  • 1≤Pi≤1001 \leq P_i \leq 100
  • 输入中的所有数值均为整数

样例解释 1

考虑以下提交策略：

  1. 首先提交第 1 题
  2. 如果提交正确，则提交第 2 题；否则再次提交第 1 题

这种情况下得分的期望值为 95 分。无法使期望值超过 95 分，因此输出 95。

翻译由 DeepSeek V3 完成

输入解题思路，AI测评打分。不知道怎么写?

首页