CFR 573 B. Bear and Blocks ( DP )

題意：
有若干個不一定相同高度的塔連續排成一排。每次操作會把滿足「上下左右其中一格子是空的」的所有單位為一的塊刪除。求幾次操作後才能將所有塔刪除。

數據範圍：
塔數 1 ≤ N ≤ 1e5
塔高度 1 ≤ H[ i ] ≤ 1e9

解法：
考慮一個塔需要經過多少操作後才被刪除。
dp[ i ] : 第 i 個塔消失所需時間
顯然，一個塔會消失若且唯若其最底層的塊會消失( 不可能會有任意時刻是最底層的塊先消失而其上面某個塊未消失 )，因此只考慮最底層的塊消失的時間。這個時間會是 min{ 該塔的高度, 左邊的底層塊消失的時間 + 1, 右邊的底層塊消失的時間 + 1 }。顯然不會有左邊的底層塊消失，對當前底層塊沒有貢獻，卻對右邊的底層塊造成貢獻的情況，所以不必考慮左邊對右邊造成貢獻，而這個貢獻哪天又回來貢獻左邊的情形，因此只需要向右和向左各更新一次即可。

時間 / 空間複雜度：
O( N )

int N;
vi H;

void init(){
    cin >> N;
    H = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> H[ i ];
}

int n;
vi h;

vi dp;

void preprocess(){
    n = N + 2;
    h = vi( n );
    for( int i = 0; i < N; ++i )
        h[ i + 1 ] = H[ i ];
    dp = vi( n );
    for( int i = 0; i < n; ++i )
        dp[ i ] = h[ i ];
    for( int i = 0; i < n; ++i )
        upmin( dp[ i + 1 ], dp[ i ] + 1 );
    for( int i = n - 1; 0 < i; --i )
        upmin( dp[ i - 1 ], dp[ i ] + 1 );
}

void solve(){
    cout << *max_element( dp.begin(), dp.end() ) << endl;
}