AtCoder ABC #233 : G - Strongest Takahashi

SRMで見てそうな問題。
https://atcoder.jp/contests/abc233/tasks/abc233_g

問題

N*Nのグリッドが与えられる。一部のセルにはブロックがある。
コストDをかけると、指定したD*Dの正方形領域のブロックを除去できる。
全ブロックを除去する最小コストを求めよ。

解法

ある矩形区間内のブロックをすべて除去するコストを、メモ化再帰なりDPで求めることを考える。

その際、

• 1つは、矩形全体を覆うような1回の処理で、全ブロックを除去する。そのコストはmax(幅, 高さ)である。
• そうでない場合、矩形を縦または横に2つに分割し、それぞれにおけるコストの和を再帰的に求めることを考える。
  • 全分割の仕方を総当たりし、総コストの最小値を取ろう。

int N;
string S[55];
int A[55][55];

int memo[55][55][55][55];

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

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

まとめ

最初フローを考えてしまった。