#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
相关
在下列比赛中: