#P6806. [2020福建冬令营]楼房搭建
[2020福建冬令营]楼房搭建
楼房搭建
题目描述
小 H 是一个建筑师,他接到了一个任务——按照计划图搭建一排楼房。计划图上从左到右给出了个非负整数,对于第 个数,它表示在 这个位置搭建出来的楼房的高度不能小于。 所有楼房的初始高度均为 。小 H 搭建楼房的方式也很特别。每次搭建耗时一个单位,他选择一对相邻楼房,让这两个楼房分别增高 1 个单位和增高 2 个单位。具体地,对于任意的 ,每一时刻他可以有以下两种搭建的方法:
-
让位置上的楼房的高度 +2,同时让 位置上的楼房 +1。
-
让位置上的楼房的高度 +1,同时让 位置上的楼房 +2。
小 H 想知道最快需要多少时间,搭建出来的这一排楼房才能满足计划图的要求?
输入格式
第一行一个整数。
第二行个整数,分别为。
输出格式
一行一个答案,表示最快需要多少时间。若无法完成搭建,输出 -1。
样例1输入
4
2 1 1 2
样例1输出
2
样例 1 解释
最开始四个楼房的高度为 0 0 0 0,小 H 最少需要如下两次搭建:
-
给第 1、2 个位置分别 +2 和 +1,高度变为 2 1 0 0。
-
给第 3、4 个位置分别 +1 和 +2,高度变为 2 1 1 2。
样例2输入
13
12 13 9 8 3 21 7 10 1 1 8 1 1
样例2输出
35
子任务
记 。
| 测试点编号 | 测试点编号 | ||||
|---|---|---|---|---|---|
| 1 | 11 | ||||
| 2 | 12 | ||||
| 3 | 13 | ||||
| 4 | 14 | ||||
| 5 | 15 | ||||
| 6 | 16 | ||||
| 7 | 17 | ||||
| 8 | 18 | ||||
| 9 | 19 | ||||
| 10 | 20 | ||||
每次只进行上述两种操作中的一种。所有 为非负整数,所有测试点的 上界如表所示。