Solution

Part I

下文提及的人都是留下的人。

性质 1：最优方案中，酒覆盖的范围内（看作强度无限）的人一定背面面对酒。

证明：

• 将「碰到的第 $k$ 个人一定背面面对酒」称为「命题对 $k$ 成立」。
• 碰到的第一个人一定背面面对，否则不合法，故命题对 $1$ 成立。
• 假设命题对 $k-1$ 成立，我们反证证明命题对 $k$ 成立：
  • 假设 $k$ 正面面对酒，可知 $k-1$ 与 $k$ 相互正面面对。
  • 若与 $k-1$ 喷的酒不相交，则 $k-1$ 可以去掉得到更优方案，不符合最优解。
  • 若相交，则不合法。
• 故命题对任意 $k$（$k\ge 1$）成立，原命题（性质 1）成立。

性质 2：将酒看作看作强度无限，答案不变。

证明：

• 根据性质一，存在最优方案在酒可以穿过人的情况下也合法，求出的答案不大于原问题答案。
• 设酒覆盖的范围为 $[l,r]$，第一个碰到的人覆盖范围为 $[l',r']$：
  • 设 $l'>l$。另一种情况有 $r'<r$，证明同理。
  • 若 $r'\le r$，则去掉第一个人可以得到更优方案，不符合最优解。
  • 故 $r'>r$，无论酒能否穿过他，两个人覆盖的区间始终为 $[l,r']$。可以穿过的情况下覆盖的区间在原问题中可以以相同步数覆盖，故求出的答案不小于原问题答案。
• 故求出的答案等于原问题答案。

接下来的讨论都默认酒的强度无限。

性质 3：最优解中，最左边的人一定覆盖了 $1$。

证明：

• 假设没有覆盖，即需要后面的人覆盖。设这个人和后面覆盖 $1$ 的人的区间分别为 $[l,r],[l',r']$。显然 $l'<l$。
• 若 $r<r'$，则最左边的人没有需要，去掉得到更优解。
• 若 $r\ge r'$，此时两人相互正面面对且有交，不合法。

Part II

考虑 DP。从左到右考虑，设 $f_{i,j}$ 为前 $i$ 个表演者覆盖了 $[1,j]$ 的最小操作数。

转移较为显然：

• 不留下：$f_{i,j}\gets f_{i-1,j}$。
• 向左：$f_{i,i}\gets\min_{j\in[i-a_i,i-1]}\{f_{i-1,j}\}+1$。
• 向右：$f_{i,i+a_i-1}\gets\min_{j\in[i-1,n]}\{f_{i-1,j}\}+1$。

注意到 $\{f_i\}$ 仅由 $\{f_{i-1}\}$ 转移来，通过滚动数组可以将问题变为单点修改与区间求 max。使用线段树维护即可。时间复杂度 $\mathcal{O}(n\log n)$。

// writer: Milkcat
// time: 2024.2.15 18:19
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int n, x, s[N << 2];
void upd(int p, int l, int r, int t, int v) {
    if (l == r) { s[p] = min(s[p], v); return; }
    int m = (l + r) >> 1;
    if (t <= m) upd(p << 1, l, m, t, v);
    if (t > m) upd(p << 1 | 1, m + 1, r, t, v);
    s[p] = min(s[p << 1], s[p << 1 | 1]);
}
int ask(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return s[p];
    int m = (l + r) >> 1, rs = 1e9;
    if (L <= m) rs = min(rs, ask(p << 1, l, m, L, R));
    if (R > m) rs = min(rs, ask(p << 1 | 1, m + 1, r, L, R));
	return rs;
}
int main() {
	cin >> n, memset(s, 0x3f, sizeof s), upd(1, 0, n, 0, 0);
	for (int i = 1; i <= n; i ++) {
		cin >> x;
		upd(1, 0, n, min(i + x - 1, n), ask(1, 0, n, i - 1, n) + 1);
		upd(1, 0, n, i, ask(1, 0, n, max(i - x, 0), i - 1) + 1);
	}
	cout << ask(1, 0, n, n, n) << '\n';
	return 0;
}