问题 22072 --SF

22072: SF

时间限制: 3 Sec  内存限制: 32 MB
提交: 3  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS3元][添加到购物车][下载测试数据3元][20kb]

题目描述

现有一条单向公路,在路的一侧种有N2<=N<=25)颗特殊花种(SF),由于天气原因,Tom只有h小时(1<=h<=16)的时间收集SF的种子,这是因为SF种子被雨淋后将失去研究价值。现在,Tom位于第1SF的位置,他可以采摘任意一株SF的种子。从第iSF到达第i+1株的位置,需要花费的时间单元个数为t(此处时间单元为5分钟),即表示花费时间Ti=5*t(其中i=0..n-1,0<Ti<=960,t=4T5=t*5=20,表示从第4SF到达第5SF需要花费20分钟)。Tom可有选择地收集途径过程SF的种子,但由于收集难度,每5分钟,他只能收集FiSF的种子(很苦哈)。天气越来较差,使得Tom在收集SF的种子过程中会掉落部分种子(更苦了,收集效率还下降),假设Tom1个时间单元掉落个数增加Di(掉落的没有收集价值,如果某SFFi小于等于Di,5分钟后,每一时间单元可收集种子个数将为0)。

Tom为了使损失最小,尽量多地收集种子,Tom需要进行简单的规划。现在请你帮他设计一程序,求取在SF种子收集数最大的前提下,Tom在每个SF停留的时间。

注意:在每个SF停留的时间,均为5的倍数。SF种子满足方案要求,即可认为种子数目极多。

输入

每组数据第1行为Nh,之后的3行为i处收集SF种子的详细情况。

(1)行为每一个时间单元,可收集第iSF种子数Fii=1..N,

(2) 行为Tom在收集第iSF种子的过程中,每一个时间单元掉落SF种子个数的增加量Dii=1..N,

(3) 行为Tom从第iSF走到第i+1株所需要花费的时间(i=1..N-1)。

数据的输入以0结束。



输出

每组数据输出2行,

1行输出在Tom需在每个SF停留的时间,

2行输出Tom可收集到最大种子数。

如果方案存在,尽可能地多的停留在第1SF(人懒哈),如果还有方案与其平局,需尽可能地停留在第2SF处,依次类推。

样例输入

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 seeds collected: 31
240, 0, 0, 0
Number of seeds collected: 480
115, 10, 50, 35
Number of seeds collected: 724

提示

来源

[提交][状态]