在盘古开天辟地之前,他需要对当前所处的地形进行调查。
盘古的面前一共有n座山,从左往右第i座山的高度为hi。
盘古会选择一段连续的山进行开辟。记他选择的区间为[l,r],盘古选择的山必须满足h1<hl+1<..<hr,也就是从左往右对应的山的高度严格单调递增。
考虑选择修改每个山的高度,如果该山的高度在它的前一座山的高度和后一座山的高度之间那么最大高度为前一座山向左延伸的最大高度+后一座山向右延伸的最大高度+1,用两个数组维护即可,注意特判第一座山和最后一座山的情况
c++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n, a[N], l[N], r[N];
本题属于以下题库,请选择所需题库进行购买