D题：Pyramid
标签：动态规划、前缀和
题意：金字塔型序列：
1
、
2...
k
−
1
、
k
、
k
−
1...2
、
1
1、2...k-1、k、k-1...2、1
1、2...k−1、k、k−1...2、1。给定一个长度为
n
n
n的序列
a
i
a_i
ai，可以进行重复性的两种操作：
- 将序列中某个数的大小减一
- 删除第一个或最后一个数
求能够形成的金字塔型序列的最大长度。（
1
<
=
n
<
=
2
∗
1
0
5
，
1
<
=
a
i
<
=
1
0
9
1<=n<=2*10^{5}，1<=a_i<=10^9
1<=n<=2∗105，1<=ai<=109）
题解：比较常见的套路，洛谷也有类似的题：P1091 合唱队形
从左往右维护一个
p
r
e
[
i
]
pre[i]
pre[i]：以
a
i
a_i
ai作为结尾的最长左金字塔序列的长度
从右往左维护一个
s
u
f
[
i
]
suf[i]
suf[i]：以
a
i
a_i
ai作为结尾的最长右金字塔序列的长度
我们以
p
r
e
[
i
]
pre[i]
pre[i]为例，分别来观察一下
例子
1
1
1：
1
、
2
、
3
1、2、3
1、2、3
例子
2
2
2：
1
、
2
、
2
1、2、2
1、2、2
例子
3
3
3：
3
、
1
、
2
3、1、2
3、1、2
按照题目中能把数变小和删除前后数字的操作，能推出当前的
p
r
e
[
i
]
pre[i]
pre[i]要从前面的
p
r
e
[
i
−
1
]
pre[i-1]
pre[i−1]和当前
a
i
a_i
ai较小的那个推过来：
p
r
e
[
i
]
=
m
i
n
(
p
r
e
[
i
−
1
]
+
1
,
a
[
i
]
)
pre[i] = min(pre[i - 1] + 1, a[i])
pre[i]=min(pre[i−1]+1,a[i])
s
u
f
suf
suf同理，最终枚举每个数作为金字塔尖，左边金字塔序列长度和右边金子塔序列长度中取小的那个能够形成的金字塔序列长度，然后维护一个最大值。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll a[N], pre[N], suf[N];
int main() {
ll n, ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = min(pre[i - 1] + 1, a[i]);
}
for (int i = n; i >= 1; i--) {
suf[i] = min(suf[i + 1] + 1, a[i]);
}
for (int i = 1; i <= n; i++) {
ans = max(ans, min(pre[i], suf[i]));
}
cout << ans;
return 0;
}
