KUPC2013 : D - カーペット

これ、途中でヒント情報を目にしてしまったんだよなぁ。
http://kupc2013.contest.atcoder.jp/tasks/kupc2013_d

問題

部屋の幅がNマス分あり、各マスにおける高さA[i]が与えられる。
この形状を長方形のカーペットを複数枚使って覆い尽くしたい。
カーペットのサイズは１枚１枚異なっていても良く、部分的に重ねても良い。

必要な最少のカーペット枚数を答えよ。

解法

問題の図を見ると思いつくのが、上から出っ張ってる部分を順に長方形を敷き詰めて消す、というもの。
消す、という処理があるのでデータ構造に迷うが、スタックを使って処理できる。

カーペットの高さを端から順に以下の様に処理していく。

• スタック上に、処理するマスの高さより高い数値が入っていたら、それらをすべてpopする。そして取り除いた数をカーペット枚数として加算する。
• スタックの最上位が、処理するマスの高さと同じなら何もせず、小さいなら処理するマスの高さをスタックにpushする。

最後に残ったスタック内の要素数だけ、カーペット枚数に加算して答えとなる。

なぜこれで行くか考えてみる。
Nマスの高さがすべて別々ならN枚のカーペットが無いと全面覆い尽くせない。
しかし、Nマスのうち同じ高さのマスがいくつかあり、かつそれらの間にそれより低いマスが無ければ、それらは１枚でまとめて処理できる。
この処理を「スタックの最上位と同じ高さならpushしない」という形で表現できている。

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	int N;
	stack<int> S;
	
	N=GETi();
	r=0;
	FOR(i,N) {
		j=GETi();
		while(!S.empty() && S.top()>j) {
			S.pop();
			r++;
		}
		if(S.empty() || S.top()<j) S.push(j);
	}
	r+=S.size();
	
	
	_P("%d\n",r);
}

まとめ

こういうマッチング系の問題はスタックを使えばいいんだな。
覚えておこう。