（FJWC2020）DTOJ 4681. 楼房搭建

本文主要是介绍（FJWC2020）DTOJ 4681. 楼房搭建，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

小 H 是一个建筑师，他接到了一个任务——按照计划图搭建一排楼房。计划图上从左到右

给出了 $n$ 个非负整数，对于第 $i$ 个数 $h_i$ ，它表示在 $i$ 这个位置搭建出来的楼房的高度不能小于 $h_i$ 。

小 H 搭建楼房的方式也很特别。在每一时刻，它总可以让相邻的两个楼房分别增高 $1$ 个单位和增高 $2$ 个单位。

具体地，对于任意的 $\le i < n)$ ，每一时刻他可以有以下两种搭建的方法：

让 $i$ 位置上的楼房的高度 $+ 2$ ，同时让 $i + 1$ 位置上的楼房 $+ 1$ 。
让 $i$ 位置上的楼房的高度 $+ 1$ ，同时让 $i + 1$ 位置上的楼房 $+ 2$ 。

小 H 想知道最快需要多少时间，搭建出来的这一排楼房才能满足计划图的要求？
$n,h[i]\le 1000000$

题解

考场上只会 $O(n^3)$ 的暴力DP，然后减个枝就立方过一千了。~~（FJ怎么回事，连续两天立方过平方的分，削减选手往下想的积极性）~~
这是道神仙贪心题。
原本想过可撤销的贪心，但没想到能这么撤销。
为了方便，转化为原本有高度h，将其铲平。
显然考虑前 $i - 1$ 个已经铲平，现在要把第 $i$ 个铲平。目前的最优解就是把 $i$ 减 $2$ ， $i + 1$ 减 $1$ ，直到若 $h [i] = 1$ ,则把 $i$ 减 $1$ ， $i + 1$ 减 $2$ （设这样的操作为 $A i$ ）。显然这对于之后可能更劣，于是考虑撤销：在 $i + 1$ 时，把 $A_i$ 变个形态，使它在 $i + 1$ 上更优，而它在 $i$ 上的作用不变：加上一个操作，变为两个把 $i$ 减1， $i + 1$ 减2，这样等于耗费1的代价使 $h [i + 1]$ 减少3（设为 $B_i+1$ ）。
现在的目的是考虑到每一个 $i$ 时，先用尽量小的代价铲平 $h [i]$ 。对于一个 $B_i$ ，发现它可以通过1的代价转到一个 $B_i+1$ ，或者通过2的代价转到两个 $B_i+1$ 。于是先做 $A, B$ 的转移（即撤销），再按照一开始的贪心即可。