【32.89%】【codeforces 574D】Bear and Blocks

time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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.

Input
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.

Output
Print the number of operations needed to destroy all towers.

Examples
input
6
2 1 4 6 2 2
output
3
input
7
3 3 3 1 3 3 3
output
2
Note
The picture below shows all three operations for the first sample test. Each time boundary blocks are marked with red color.

After first operation there are four blocks left and only one remains after second operation. This last block is destroyed in third operation.

【题目链接】:http://codeforces.com/contest/574/problem/D

【题解】

设l[i]表示把从左到右把第i列完全消去需要的操作数;
h[i]次操作是肯定能够把第i列消去的;因为这一列的最上面那个方块总是暴露出来的；
l[i-1]+1
第i列消掉之后可以直接把第i列消去,因为i-1列完全消掉之后,第i列整个左面就暴露出来了；如何保证消掉第i列一定要+1?第i-1列消掉用了l[i-1]次操作,如果l[i-1]>=h[i]则不用加1,因为在消第i-1列的时候就顺带把第i列消掉了;事实上这种情况l[i]=h[i];否则的话
l[i-1] < h[i];则先操作l[i-1]次把i-1这一列完全消掉;然后第i列剩下的方块左边全部暴露出来;剩下的就可用一次操作完全消掉了;所以是l[i-1]+1;
即l[i] =(l[i-1]+1,h[i])min
边界l[1] = 1;
但这样只考虑了左面暴露的情况;
有可能右面暴露更优;
比如
h[] = {1,2,3,4,5};
只考虑从左到右的话,l[] = {1,2,3,4,5};
但是消掉第5列显然只要1次,消掉第4列显然只要两次操作;
所以咱们从右到左也进行相同的DP;
处理出r[];
最后每个位置i都取min即可;
然后所有位置的最大值就是答案(所有的列都要消掉,时间最长的就是答案);

【完整代码】

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+10;

int n,h[MAXN],l[MAXN],r[MAXN];

int main()
{
    //freopen("F:\rush.txt","r",stdin);
    scanf("%d",&n);
    for (int i = 1;i <= n;i++)
        scanf("%d",&h[i]);
    l[1] = 1;
    for (int i = 2;i <= n;i++)
        if (l[i-1]>=h[i])
            l[i] = h[i];
        else
            l[i] = l[i-1]+1;
    r[n] = 1;
    for (int i = n-1;i >= 1;i--)
        if (r[i+1] >= h[i])
            r[i] = h[i];
        else
            r[i] = r[i+1]+1;
    int ans = 1;
    for (int i = 1;i <=n;i++)
        ans = max(ans,min(l[i],r[i]));
    cout << ans << endl;
    return 0;
}