Codeforces Round #318-(D. Bear and Blocks)

Codeforces Round #318-(D. Bear and Blocks)

這道題我上來就是想到的是暴力，每次都把表面的那一層減掉，直到所有的高度為0為止。但是T了。

題意：

現在有n個方格，然後每個方格都有一個高度，然後每次都可以把那些非完整塊（就是它的四個方向沒有被完全包圍）給連在一起消去。問你最後把所有的方塊消去需要幾次。

思路：

我們只需要從左邊，右邊分別進行一次消去，然後最後進行一次判斷就好了。最多的次數不可能超過最大的那個的高度。

首先初始化為h1[0]=0,h2[n+1]=0, 我們設兩個數組h1代表的是從左邊開始消去每次的最大高度，h2則是右邊的。

h1[i]=min(h[i],h1[i-1]+1);

h2[i]=min(h[i],h2[i+1]+1);

這兩個方程應該想一下就能明白的。我們每次當然應該滿足高度較小的那個。

#include
#include
#include
#include
#include
#include
using namespace std;
#define inf 99999999
#define maxn 100010
int h[maxn];
int h1[maxn],h2[maxn];
int main(){
	int n;
	scanf(%d,&n);
	for(int i=1;i<=n;i++) scanf(%d,&h[i]);
	int ans=0;
	h1[0]=0;
	for(int i=1;i<=n;i++){
		h1[i]=min(h[i],h1[i-1]+1);
	}
	h2[n+1]=0;
	for(int i=n;i>=1;i--){
		h2[i]=min(h[i],h2[i+1]+1);
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,min(h1[i],h2[i]));
	}
	printf(%d
,ans);
}