NC21347. 杀猪刀
描述
听说时间是把杀猪刀，又听说一寸光阴一寸金，千金难买寸光阴
那么杀猪刀就很值钱，恩，没错，就是这样
于是牛牛决定开始兜售杀猪刀吸金，假设牛牛有swords把杀猪刀，为了多赚点钱，牛牛决定24小时营业
牛牛事先做过市场调研，肯买杀猪刀的顾客是一批特殊的顾客,他们会根据自己对时间的价值判断给出自己要买的杀猪刀的价格
(概率以百分比的形式给出)
顾客的信息按照如下格式给出
....
第i行表示第i个顾客的信息
假设第i行的信息为T1,C1,P1 T2,C2,P2 ... TN,CN,PN
第i行的第j个三元组Tj,Cj,Pj表示 i 顾客会有Pj的概率在Tj时前来购买杀猪刀,并且愿意付出Cj的价格
第i个顾客不来店里的概率为100-(P1+P2+..+PN)
同一个顾客不会来店里超过一次，每一个小时只会有一个顾客来购买杀猪刀，一个顾客只会买一把杀猪刀
当一个顾客来的时候，牛牛可以选择卖或者不卖，假设最终他赚的钱为S，牛牛希望求出S的最大期望值
那么杀猪刀就很值钱，恩，没错，就是这样
于是牛牛决定开始兜售杀猪刀吸金，假设牛牛有swords把杀猪刀，为了多赚点钱，牛牛决定24小时营业
牛牛事先做过市场调研，肯买杀猪刀的顾客是一批特殊的顾客,他们会根据自己对时间的价值判断给出自己要买的杀猪刀的价格
(概率以百分比的形式给出)
顾客的信息按照如下格式给出
....
第i行表示第i个顾客的信息
假设第i行的信息为T1,C1,P1 T2,C2,P2 ... TN,CN,PN
第i行的第j个三元组Tj,Cj,Pj表示 i 顾客会有Pj的概率在Tj时前来购买杀猪刀,并且愿意付出Cj的价格
第i个顾客不来店里的概率为100-(P1+P2+..+PN)
同一个顾客不会来店里超过一次，每一个小时只会有一个顾客来购买杀猪刀，一个顾客只会买一把杀猪刀
当一个顾客来的时候，牛牛可以选择卖或者不卖，假设最终他赚的钱为S，牛牛希望求出S的最大期望值
输入描述
第一行输入两个整数n,swords 表示顾客与刀的数量(1 ≤ n ≤ 24, 1 ≤ swords ≤ 24)
接下来n行每行输入一行字符串表示每个顾客的信息,字符串的长度在[5,50]范围内
比如
"T1,C1,P1 T2,C2,P2 ... TN,CN,PN" (Tj,Cj,Pj都是非负整数)
0 ≤ Tj ≤ 23, 1 ≤ Cj ≤ 100, 1 ≤ Pj ≤ 100
对于每个顾客T1 < T2 < T3.. < TN, P1 + P2 + ... + PN <= 100
对于每一个t (0<=t <24), 最多有一对(i,j) ，顾客i的 Tj = t
输出描述
输出一个浮点数，误差在1e-9以内
示例1
输入:
2 1 8,1,80 16,100,11 12,10,100
输出:
19.0
说明:
因为你可以选择卖或者不卖，不是随机的卖或者不卖，因此期望赚钱的数量就存在一个最优决策情况只有一把刀
8:00第一个顾客假如来的话不卖，由于知道了16:00他肯定不会再来了，那就12:00卖出给第二个顾客 期望得分0.8 * 1.0 * 10
8:00第一个顾客假如不来,因为我知道16:00的时候第一个顾客可能会来，12:00的时候我就不卖，等到16:00的时候第一个顾客来的时候再卖,期望得分0.11 * 100（如果在12:00的时候卖给第二个顾客期望得分为0.2*10）
如果16:00第一个顾客也没来，时间不能倒流，只能不卖了 ，期望得分0 * 0.09
综上，最优决策是0.8*10 + 0.11*100 = 19
示例2
输入:
2 2 8,1,80 16,100,11 12,10,100
输出:
21.8
说明:
有两把刀8:00第一个顾客来的话卖出一把，12:00卖出一把 0.8 * 11
8:00第一个顾客不来，12:00卖出一把0.2*10 , 16:00假如第一个顾客来，再卖出一把100 * 0.11
第一个顾客16:00也不来，0.09 * 0
所以一共是0.8 * 11 + 0.2*10 + 100 *0.11 = 21.8
示例3
输入:
2 1 0,90,25 2,90,25 4,90,25 6,90,25 7,100,80
输出:
90.0
示例4
输入:
4 3 17,31,41 20,59,26 23,53,5 19,89,79 16,32,38 22,46,26 18,43,38 21,32,7
输出:
135.5121414
示例5
输入:
10 5 1,1,10 2,2,9 3,3,8 4,4,7 5,5,6 6,6,5 7,7,4 8,8,3 9,9,2 10,10,1
输出:
2.1999744634845344