Limak is a little bear who loves to play. Today he is playing by destroying block towers. He built n towers in a row. The i-th tower is made of hi identical blocks. For clarification see picture for the first sample.
Limak will repeat the following operation till everything is destroyed.
Block is called internal if it has all four neighbors, i.e. it has each side (top, left, down and right) adjacent to other block or to the floor. Otherwise, block is boundary. In one operation Limak destroys all boundary blocks. His paws are very fast and he destroys all those blocks at the same time.
Limak is ready to start. You task is to count how many operations will it take him to destroy all towers.
The first line contains single integer n (1 ≤ n ≤ 105).
The second line contains n space-separated integers h1, h2, ..., hn (1 ≤ hi ≤ 109) — sizes of towers.
Print the number of operations needed to destroy all towers.
6 2 1 4 6 2 2
3
7 3 3 3 1 3 3 3
2
The picture below shows all three operations for the first sample test. Each time boundary blocks are marked with red color.
题目大意：有n列方块，给出每一列的高度$h_i$，如果一个方块在它四周有至少一个方向没有方块，那么它可以被去除。每次操作去除所有可去除的方块，求几次操作后可以去掉所有方块。
暴力必然超时。一次操作对第i列的影响可以表示为$h_i=\min\left(h_{i-1},h_i-1,h_{i+1}\right)$。进行k次操作后的高度可以这样表示：令$Left=\min\left(h_{i-j}-\left(k-j\right)\right)\left(1\leq j\leq k\right)$，Right也是类似的，则$h_i=\max\left(0,\min\left(Left,Right\right)\right)$。当$k=\min\left(h_{i-j}+j\right)$时Left取到0，Right类似。所以对于每一列求出它最小的k，然后每一列的k的最大值就是答案。
代码在此。
评论 (0)
