CF573B Bear and Blocks 题解

这道题有一点思考难度，需要根据题意与样例来思考。

首先我们考虑 \(a_i\) 在几次之后会降为 0。

接下来的分析只考虑这个柱子上面被摧毁的情况，不考虑左右的柱子高度为 0 的影响。

1. 如果 \(a_i \leq a_{i - 1}\) 且 \(a_i \leq a_{i + 1}\)，那么只有最上面的格子会遭殃，消耗次数 \(a_i\)。
2. 否则，\(a_i = \min{(a_{i - 1}, a_{i + 1})}\)，此时我们可以通过暴力计算。

但是有没有更好的方法呢？

我们知道对于这种求最小值的题目，通常都可以使用 dp 来解决。

设 \(f_i\) 为第 \(i\) 根柱子被摧毁的次数，那么根据上面的分析，我们有状态转移方程：$$f_i = \max{(f_{i - 1} + 1, a_i, f_{i + 1} + 1)}$$

考虑到对于 \(f_i\) 需要同时用到左右两边的数据，那么我们可以做两遍 dp 来解决。

那么现在再来考虑左右两边的情况。

其实我们只要在左右两边加上一根高度为 0 的虚拟柱子不就好了qwq。

代码：

#include 
#define Max(a, b) ((a > b) ? a : b)
#define Min(a, b) ((a < b) ? a : b)
using namespace std;

typedef long long LL;
const int MAXN = 1e5 + 10;
int n, a[MAXN], f[MAXN], ans;

int read()
{
	int sum = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
	return sum * fh;
}

int main()
{
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int i = 1; i <= n; ++i) f[i] = Min(f[i - 1] + 1, a[i]);
	for (int i = n; i >= 1; --i) f[i] = Min(f[i + 1] + 1, f[i]);
	for (int i = 1; i <= n; ++i) ans = Max(ans, f[i]);
	printf("%d\n", ans);
	return 0;
}