这场食戟我要赢

Time Limit
2s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
55.56%(5/9)
Description:

 

幸平创真,远月厨师学校的一名插班生,因善于在食物中下药(划掉)厨艺精湛而轰动校园。

不久他将迎来和学院十杰之一的绘里奈的厨艺对决,远月师生将其称之为食戟对决,是赌上各自最重要东西的比赛,为了赢得食戟,创真要开始认真准备食材了。

这次的主题是秋刀鱼,为了食材的新鲜和质量,创真决定亲自去钓鱼,但是距离比赛他只有有限的时间h小时(1 <= h <= 16),他需要有一种方案能钓到尽可能多的鱼。

钓鱼的地方共有n(2 <= n <= 25)个湖,所有的湖沿着一条单向路顺序排列(创真每在一个湖钓完鱼后,他只能走到下一个湖继续钓),创真必须从1号湖开始钓起,但是他可以在任何一个湖结束他此次钓鱼的行程。

我们以5分钟作为单位时间,创真在每个湖中每5分钟钓的鱼数随时间的增长而线性递减。每个湖中头5分钟可以钓到的鱼数用fi(fi >= 0)表示,每个湖中相邻5分钟钓鱼数的减少量用di(di >= 0)表示,创真从任意一个湖走到它下一个湖的时间用ti个时间单位(0 <= ti <= 192)表示。

Input:

 

多组数据,第一行为n0代表结束)。

第二行为h

第三行顺序输入fi

第四行顺序输入di

第五行顺序输入ti

Output:

 

对于每组数据,输出能钓到最多鱼的最佳方案(注意格式)并用空行隔开:

第一行输出每个湖停留的分钟数,并用逗号隔开。

第二行输出钓鱼总数。

如果有多种方案,则选择在1号湖耗时最多的方案。如果仍不唯一,则选择其中在2号湖耗时最多的方案,以此类推。

Sample Input:
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 
Sample Output:
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
Source:

poj


Submit