钓鱼
成绩 | 100 | 开启时间 | 2020年02月20日 星期四 20:20 |
折扣 | 0.8 | 折扣时间 | 2020年02月20日 星期四 20:20 |
允许迟交 | 是 | 关闭时间 | 2020年02月20日 星期四 20:20 |
输入文件 | fish.in | 输出文件 | fish.out |
【题目描述】钓鱼(fish)POJ 1042
已知在一条水平路边,有 n(2≤n≤25)个池塘,从左到右编号为1,2,3,…,n。小光有H(1≤H≤16)个小时的空闲时间,他只能从第一个池塘开始向右走,可以在每个池塘中钓鱼,每个池塘第一个5分钟可以钓到鱼fi,以后再每钓5分钟,鱼量减少di,且从池塘到下一个池塘之间都有一定的距离5×Ti,例如Ti=4,则距离为20。知道了每个池塘走到下一个池塘的时间和每个池塘一开始能够钓鱼的数量,求在规定的时间内所能钓到的最多的鱼的数量。
【输入格式】
有多组测试数据,每组数据第一行为整数n。第二行为H,随后一行为fi (1≤i≤n), 接下来一行为di(1≤i≤n),最后为n-1个整数ti(1≤i≤n-1),n=0表示结束。
【输出格式】
对于每组数据,第一行输出在每个池塘花费的时间,第二行输出钓到的最多鱼的数量。若有多种方案,选择在第一个池塘花费时间最多的方案,若第一个池塘没有钓到鱼,则选择在第二个池塘花费时间最多的方案,以此类推。每组方案以空行间隔。
【输入样例】
2
1
10 1
2 5
2
4
4
10 15 20 17
0 3 4 3
1 2 3
4
4
10 15 50 30
0 3 4 3
1 2 3
0
【输出样例】
45, 5
Number of fish expected: 31
240, 0, 0, 0
Number of fish expected: 480
115, 10, 50, 35
Number of fish expected: 724