#CW19. 消除环(cycle)
消除环(cycle)
题目描述
给定一个长度为 的整数序列 ,这些元素首尾相连,形成一个环。也就是, 与 相邻(), 和 相邻。
你要按照一定的规则消除这个环中的所有元素。
初始时,你有一个能力值 。对于每次要消除的元素 ,必须满足:。
你可以任意选择一个元素作为第一个元素来首先消除。除了第一个元素可以任意选择以外,之后,每次只能选择当前仍存在的、至多有一个相邻元素尚未被消除的元素。
消除一个元素 后,能力值立即增加其数值:。
求消除整个环所需的最小初始能力值 。
输入格式
第一行一个整数 ,表示序列长度。
第二行 个整数 。
输出格式
输出一个整数,表示最小的初始能力值 。
样例 1 输入
5
5 0 10 6 1
样例 1 输出
4
样例 2 输入
7
20 23 7 2 3 7 1
样例 2 输出
2
数据范围
对于所有测试数据,保证:,。
| 分值 | 特殊性质 | |
|---|---|---|
| 无 | ||
| 无 |
本题按 subtask 计分:只有通过一个 subtask 的全部测试点,才能获得该 subtask 的分数。