问题 1269 --钓鱼

1269: 钓鱼

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

“我现在有点相信你所说的话了，但是一想到你所描述的未来的我，总有一种虚幻而不真实的感觉。”小墨老师犹豫不决。

“你只要保持坚定的信念，并努力去做，你就一定能成为我所说的未来领导者的。其实每个人都有无穷无尽的潜力，只要你能好好地利用它。”李旭琳鼓励他。

“哦，我想要去钓鱼静静心，顺便好好思考一下。”小墨老师最后说。

已知在一条水平路边，有 n（2≤n≤25）个池塘，从左到右编号为１，２，３，…，n。小墨老师有Ｈ（1≤H≤16）个小时的空闲时间，他只能从第一个池塘开始向右走，可以在每个池塘中钓鱼，每个池塘第一个五分钟可以钓到鱼fi，以后再每钓五分钟，鱼量减少Di，且从池塘到下一个池塘之间都有一定的距离５×Ｔi，例如Ｔi=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

提示

来源

贪心 

[提交][状态]