kmjp's blog

競技プログラミング参加記です

Codeforces #576 Div1 D. Rectangle Painting 1

うーん、Cより先にこっちやればよかったか。
https://codeforces.com/contest/1198/problem/D

問題

白黒で塗られたグリッドが与えられる。
ここで、ある矩形範囲を白く塗りつぶすために必要なコストは幅と高さの大きい方とする。

グリッド全体を白くするのに必要なコストを求めよ。

解法

ある矩形内を塗りつぶすすコストをメモ化再帰で求めよう。
複数回の塗りつぶし方を重ねるのはコスト的に意味がない。両者を包含する大きな矩形を1手で塗りつぶす方が良いためである。
よって区間の塗りつぶし方は以下のいずれか。

  • 1手で全体を塗りつぶす
  • 縦か横に区切ってそれぞれ最小化する

あとはこれを愚直に行えば状態がO(N^4)、状態遷移がO(N)でO(N^5)で解ける。

int N;
string S[51];
int memo[51][51][51][51];
int SS[51][51];

int hoge(int L,int R,int T,int D) {
	if(memo[L][R][T][D]>=0) return memo[L][R][T][D];
	if(SS[D][R]-SS[T][R]-SS[D][L]+SS[T][L]==0) return memo[L][R][T][D]=0;
	int ret=max(D-T,R-L);
	
	int x,y;
	for(x=L+1;x<R;x++) ret=min(ret,hoge(L,x,T,D)+hoge(x,R,T,D));
	for(y=T+1;y<D;y++) ret=min(ret,hoge(L,R,T,y)+hoge(L,R,y,D));
	
	
	
	return memo[L][R][T][D]=ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>S[y];
		FOR(x,N) {
			SS[y+1][x+1]=SS[y][x+1]+SS[y+1][x]-SS[y][x]+(S[y][x]=='#');
		}
	}
	MINUS(memo);
	
	cout<<hoge(0,N,0,N)<<endl;
	
	
}

まとめ

うーん、もったいない。