Codeforces #256 Div2 C. Painting Fence

CF#256に参加。
Div2回ということで気楽に参加できたこともあり、全完で良い順位が取れた。
http://codeforces.com/contest/448/problem/C

問題

横幅Nメートルのフェンスがある。
このフェンスは幅1メートル高さA[i]メートルの板を横にN枚つなげて作られている。

このフェンスに刷毛で色を塗りたい。
刷毛は横または縦に幅1メートルの長方形の範囲を塗ることができる。ただしフェンスが存在しない町域を含むことはできない。
同じ領域を複数回刷毛で塗ってもよい。

フェンスの全領域を色で塗るのに、最小で何回刷毛を使う必要があるか。

解法

A[L]～A[R]の範囲を塗る最小回数を考えると、以下のいずれか小さい方である。

• 全領域を縦に塗る。これはR-L+1回ですむ。
• A[L]～A[R]のうち最低の高さのところまで横に塗り、残りについては再帰的に塗る回数を求める。

L,Rの組み合わせは一見(N^2)に見えるが、実際は取りえる組み合わせはO(N)しかないので、最低の高さをO(N)で求めても全体でO(N^2)で終わる。

int N;
int A[10000];


ll dodo(int L,int R,int H) {
	if(L>R) return 0;
	vector<pair<int,int> > V;
	
	int mi=1000000001,x;
	for(x=L;x<=R;x++) mi=min(mi,A[x]);
	int ret=mi-H;
	int pre=-1;
	for(x=L;x<=R+1;x++) {
		if(A[x]>mi && pre==-1) pre=x;
		if(A[x]<=mi && pre>=0) {
			ret+=dodo(pre,x-1,mi);
			pre=-1;
		}
	}
	return min(R-L+1,ret);
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	cout << dodo(0,N-1,0) << endl;
}

まとめ

一見迷うDPだけど、わかってしまえばすんなり。