Codeforces #318 Div1 B. Bear and Blocks

無駄に難しく考えすぎた。
http://codeforces.com/contest/573/problem/B

問題

1*1のブロックを積み上げた塔が1列にN個並んでいる。
左端からブロックの高さはH[i]である。

これらのブロック群に対し、以下の処理を行う。

• 上または左右のいずれかに他のブロックがないブロックを同時に取り除く。

全ブロックを取り除くまで、何回処理が必要か。

解法

i列目のブロックを取り除くまでの処理回数P[i]は、結局i列目の最下段のブロックを取り除くまでの処理回数に一致するので以下の最小値である。

• 上にブロックがなくなるケースを考えるとH[i]回目。
• 左にブロックがなくなるケースを考えるとP[i-1]+1回目。
• 右にブロックがなくなるケースを考えるとP[i+1]+1回目。

Pに関して前からと後ろから2周DPすれば各P[i]が確定するので、その最大値を答えればよい。

int N;
ll H[101010];
ll step[101010];
ll ma=0;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>H[i+1], step[i+1]=H[i+1];
	N+=2;
	
	
	FOR(i,N) if(i) step[i]=min(step[i],step[i-1]+1);
	for(i=N-1;i>=0;i--) step[i]=min(step[i],step[i+1]+1);
	cout<<*max_element(step,step+N)<<endl;
	
}

まとめ

本番無駄にSegTreeとか使っちゃった。