CF 573B

Bear and Blocks

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard 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 h_i 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 ≤ 10⁵).

The second line contains n space-separated integers h₁, h₂, ..., h_n (1 ≤ h_i ≤ 10⁹) — sizes of towers.

Output

Print the number of operations needed to destroy all towers.

题意：就是给你N个高度，每次删除和外界相接触的方块，问多少次可以删完

竟然是Dp

对于每一个高度，其决定值得是两边的高度，然而直接暴力T了，应该Dp

Dp【i】表示第i个高度在第几秒会被完全删完

从左往右考虑一次，从右往左考虑一次

然后对于每个 Dp值取min，所有值取MAX；

（感谢学长ChildOfHulu♂指导）

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + ;

int Num[maxn];

int Dp[maxn];

int Dp2[maxn];

set<int> S;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n;

    cin >> n;

    for(int i = ; i <= n; ++i)

    {

        //int t;

        cin >> Num[i];

    }

    for(int i = ; i <= n; ++i)

        Dp[i] = min(Dp[i-]+,Num[i]);

    for(int i = n; i >= ; i--)

        Dp2[i] = min(Dp2[i+]+,Num[i]);

    int ans = ;

    for(int i = ; i <= n; ++i)

        ans = max(ans, min(Dp[i],Dp2[i]));

    cout << ans << endl;

}

巴特西

CF 573B

最新文章

热门文章