一列火车有一个火车头拖着一长串的车厢,每个车厢有若干个乘客。一旦火车头出了故障,所有的车厢就只能停在铁轨上了,因此铁路局给每列火车配备了三个迷你火车头,每个迷你火车头可以拖动一定数量的车厢,以便火车头发生故障后能够拖走部分车厢。
铁路部门对迷你火车头作了如下规定:
1.迷你火车头能够拖动的最大车厢数是确定的,这个数量对三个迷你火车头都是相同的。
2.一旦火车头发生故障,迷你火车头要拖走尽可能多的旅客,每节车厢的旅客数事先是已知的,并且旅客不得随意更换车厢。
3.一个迷你火车头拖走的车厢必须是连续的,所有车厢从1开始编号。
假如有7节车厢,一个迷你火车头最多可以拖动二节车厢,1到7号车厢中的旅客人数分别为35,40,50,10,30,45和60。
如果三个迷你火车头拖走的车厢分别是1-2,3-4和6-7,它们带走的旅客总数将达到240人,其它任何方案都不可能超过该数,所以240就是这个问题的解。
给定车厢数,每节车厢的旅客人数和一个迷你火车头能拖动的最大车厢数,写一个程序求出三个迷你火车头最多能带走的旅客数。