#3326. 付费提交

付费提交

题目描述

在将来,参加的比赛都需要给钱。

这些比赛共有N道题目。第i道题目的分值为Si分,每次提交需要花费Ci美元。

当huhe的后代提交第i道题目时,他有Pi%的概率能够解决该题目。每次提交的结果相互独立。

huhe的后代拥有X美元。他不能进行任何会导致总花费超过X美元的提交。

请计算在他选择最优提交策略以最大化期望总分时,能够获得的期望总分值。

他可以根据前一次提交的结果决定下一步提交哪道题目。同一道题目被多次解决时,分值仅计算一次。

输入格式

  • 第一行包含两个整数N和X,分别表示题目数量和初始资金。
  • 接下来的N行,每行包含三个整数Si、Ci和Pi,分别表示第i道题的分值、提交费用和解决概率(百分比)。

约束条件

  • 1 ≤ N ≤ 8
  • 1 ≤ Si ≤ 2718
  • 1 ≤ Ci ≤ X ≤ 5000
  • 1 ≤ Pi ≤ 100
  • 所有输入均为整数。

输出格式

输出期望总分值。若你的答案与标准答案的绝对误差或相对误差不超过1e−6,则视为正确。

样例

样例输入1

3 2
100 1 50
200 1 20
1000 1 1

样例输出1

95

解释

最优提交策略如下: 首先提交第1道题目。

  • 如果提交成功,则提交第2道题目;
  • 如果失败,则再次提交第1道题目。 此策略的期望总分为95分。没有其他策略能超过此期望值,因此输出95。

状态定义:f[i][j]表示剩余资金i,已解决问题集合j时的最大期望得分

初始状态:f[2][0]=0

转移:

选择第1题:

成功:f[1][1]=100,然后选择第2题:

成功:f[0][3]=300

失败:f[0][1]=100

期望=0.2300+0.8100=140

失败:f[1][0]=0,然后再次选择第1题:

成功:f[0][1]=100

失败:f[0][0]=0

期望=0.5100+0.50=50

总期望=0.5140+0.550=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