#P6806. [2020福建冬令营]楼房搭建

    ID: 6629 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划线性 DP贪心反悔贪心模拟与实现技巧添加哨兵CF2500

[2020福建冬令营]楼房搭建

楼房搭建

题目描述

小 H 是一个建筑师,他接到了一个任务——按照计划图搭建一排楼房。计划图上从左到右给出了nn个非负整数,对于第ii 个数hih_{i},它表示在ii 这个位置搭建出来的楼房的高度不能小于hih_{i}。 所有楼房的初始高度均为 00。小 H 搭建楼房的方式也很特别。每次搭建耗时一个单位,他选择一对相邻楼房,让这两个楼房分别增高 1 个单位和增高 2 个单位。具体地,对于任意的 i(1≤i<n)i(1\le i<n),每一时刻他可以有以下两种搭建的方法:

  1. 让ii位置上的楼房的高度 +2,同时让i+1i+1 位置上的楼房 +1。

  2. 让ii位置上的楼房的高度 +1,同时让i+1i+1 位置上的楼房 +2。

小 H 想知道最快需要多少时间,搭建出来的这一排楼房才能满足计划图的要求?

输入格式

第一行一个整数nn。

第二行nn个整数,分别为h1,h2,⋯ ,hnh_{1},h_{2},\cdots ,h_{n}。

输出格式

一行一个答案,表示最快需要多少时间。若无法完成搭建,输出 -1。

样例1输入

4
2 1 1 2

样例1输出

2

样例 1 解释

最开始四个楼房的高度为 0 0 0 0,小 H 最少需要如下两次搭建:

  1. 给第 1、2 个位置分别 +2 和 +1,高度变为 2 1 0 0。

  2. 给第 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

子任务

记 hmax=max⁡{h1,h2,⋯ ,hn}h_{max}=\max\{h_{1},h_{2},\cdots ,h_{n}\}。

测试点编号 nn hmaxh_{max} 测试点编号 nn hmaxh_{max}
1 ≤3\le 3 11 ≤103\le 10^{3}
2 ≤5\le 5 12
3 ≤7\le 7 13
4 ≤9\le 9 14
5 ≤13\le 13 15 ≤106\le 10^{6}
6 ≤30\le 30 16
7 ≤300\le 300 17
8 18
9 19
10 20

每次只进行上述两种操作中的一种。所有 hih_i 为非负整数,所有测试点的 n,hmaxn,h_{max} 上界如表所示。