CodeForces - 1313C2 Skyscrapers (hard version)(单调栈+dp)
题目链接：点击查看
题目大意：给出 n 块连续的空地可以建造摩天大楼，政府有规定，每块地最高只能建 a[ i ] 的高度，同时每栋大楼需要满足一个规则，即每栋大楼的两侧不允许同时存在比自己高的大楼，输出一种方案，使得总高度之和最大
题目分析：C1题目的数据范围是 1e3 ，直接两层 for 暴力枚举每个位置作为最高点就可以了，没有难度的暴力就不多说了，直接说一下C2题目的 5e5 该如何处理吧
看到 5e5 这个数字，再看到题目给出了 3 秒的时限，第一反应肯定是摒弃 n * n 的算法，从而需要思考能否在O(n),O(nlogn)或O(nsqrt(n))中做出选择，赛后看牛客的群中有大牛用了nsqrt(n)分块的做法做出来了所以提一嘴。。其实比赛的时候队友已经想出该如何用 dp O(n) 维护答案了，设dp1[ i ]为正着到第 i 个位置为最高点的最大高度和，dp2[ i ]为反着到第 i 个位置为最高点的最大高度和，预处理完两个dp数组后，就可以O(n)枚举每个位置作为最高点，并且O(1)获得此时的贡献了，此时确定好最高点的位置剩下的输出就不多说了，现在的问题转换为了如何预处理出两个dp数组，其实不难，以dp1为例，当处理到dp[ i ]时，我们只需要找到一个位置 pos ，这个位置是位置 i 左边第一个比 a[ i ] 小的位置，此时 dp[ i ] = dp[ pos ] + ( i - pos ) * a[ i ] ，怎么解释呢，因为 pos 是位置 i 左侧第一个比 a[ i ] 小的位置，所以区间 ( pos , i ] 内的所有高度一定是大于等于 a[ i ] 的，因为我们的dp数组是求以点 i 为最高点时的最大高度和，所以点 i 的高度肯定是最大高度了，显然区间 ( pos , i ] 内的所有点都赋值为 a[ i ] 是最优的，而此时再累加上dp[ pos ]的答案便是当前点 i 的答案了
剩下的问题就变的很简单了，如何求出每个点左边以及右边第一个小于自己的位置呢，单调栈的基础应用，直接套上模板，O(n)维护出位置就可以了，总的时间复杂度为O(n)，带着一点常数无伤大雅
代码的话别看着很长，其实复用的部分很多，实际的编程复杂度充其量也只有一半多一点吧，剩下的都是CV大法了
代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
作者：Frozen_Guardian
