#P18259. Cows
Cows
Cows
一片狭长的牧场被分成连续编号为 的 个区段。第 个区段的草最初高为 ,每个区段里有一头牛。
区段之间有围栏,牛不能走到其他区段,但可以把头伸过围栏吃相邻区段的草。对于 ,第 与第 个区段相邻;首尾区段不相邻。
每一分钟,所有牛同时行动。 每头牛按照这一分钟开始时的草高选择一个区段:
- 如果自己的区段还有草,这头牛必须吃自己区段的草。
- 否则,它选择一个仍有草的相邻区段吃草。
- 如果自己和相邻区段都没有草,它就不做任何事。
如果某一分钟有 头牛吃同一个区段的草,该区段的草高减少 ,但不会低于 ,即更新为 。这一分钟吃完草的牛,要到下一分钟才可能帮助相邻区段。
所有牛相互合作,希望尽快吃完牧场中的全部草。求至少需要多少分钟。
输入格式
第一行包含一个整数 ,表示区段数量。
第二行包含 个整数 ,表示各区段最初的草高。
输出格式
输出一个整数,表示吃完全部草所需的最少分钟数。
数据范围
- ;
- ;
- 至少有一个 ;
- 输入只有一组数据。
样例 1
5
5 4 0 4 6
4
一种最优策略如下,数组表示各分钟开始前或完成后的草高:
- 初始为 。第3头牛选择第4段,其他牛吃自己的草,得到 。
- 第3头牛继续选择第4段,得到 。
- 第3头牛选择第2段,第4头牛选择第5段,得到 。
- 第2头牛选择第1段,第4头牛选择第5段,第3头牛不行动,得到 。
样例 2
3
1 4 6
5
本例中牛始终没有选择余地,过程为
$$[1,4,6]\to[0,3,5]\to[0,1,4]\to[0,0,3]\to[0,0,1]\to[0,0,0].$$