Codeforces Round 318 (Div. 2) D - Bear and Blocks

题意：有n列方块，每列方块的高度为$a_i$，现在有一个操作：每次操作时把外围的方块消去（内部方块的定义：内部方块的四个方向上下左右都有方块或地板，这些方块为内部方块，其他方块为外部方块），问需要多少次操作可以将所有方块消去

先考虑普遍情况
3
1 2 1
这种情况只需要2个步骤
5
1 2 3 2 1
这种情况只需要3个步骤
7
1 2 3 4 3 2 1
这种情况只需要4个步骤
所以。。只需要找这n列中的这些部分中最大的那个部分高度，就是需要的操作次数

//author: CHC
//First Edit Time:	2015-09-09 12:55
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 100;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int A[MAXN],n;
int dl[MAXN],dr[MAXN];
int main()
{
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)scanf("%d",&A[i]);
        dl[0]=0;
        for(int i=1;i<=n;i++)dl[i]=min(dl[i-1]+1,A[i]);
        dr[n+1]=0;
        for(int i=n;i>=1;i--)dr[i]=min(dr[i+1]+1,A[i]);
        int ans=0;
        for(int i=1;i<=n;i++)ans=max(ans,min(dl[i],dr[i]));
        printf("%d\n",ans);
    }
    return 0;
}