UVa-10667 : Largest Block

問題概要

W*W(W<100)の0,1が入ったボードがある。最大の0のみからなる部分長方形の面積を求める問題。

解法

もっとも愚直にやるとW^4。両端を固定して考えるとW^3で、通すだけならこれで十分。実はW^2で解くことができる。各行について蟻本p280の問題に落とせばよい。

acceptされたコード

ボードを構成する部分がボトルネックで計算量(N*W^2)。ただしもう少し速くなるとは思う(平方分割とかsegtreeとか)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_W = 100;

int W, N;
int as[MAX_W], bs[MAX_W], Ls[MAX_W], Rs[MAX_W], stack[MAX_W];
bool board[MAX_W][MAX_W];

void init(){
	scanf("%d%d", &W, &N);

	memset(board, false, sizeof(board));
	for(int i=0; i<N; i++){
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
		for(int y=y1-1; y<y2; y++){
			for(int x=x1-1; x<x2; x++){
				board[y][x] = true;
			}
		}
	}

}

int calc(){
	int st = 0;
	for(int i=0; i<W; i++){
		for(;st>0 && as[stack[st-1]] >= as[i]; st--);
		Ls[i] = (st == 0 ? 0 : (stack[st-1] + 1));
		stack[st++] = i;
	}

	st = 0;
	for(int i=W-1; i>=0; i--){
		for(;st>0 && as[stack[st-1]] >= as[i]; st--);
		Rs[i] = (st == 0 ? W : stack[st - 1]);
		stack[st++] = i;
	}

	int ans = 0;
	for(int i=0; i<W; i++){
		ans = max(ans, as[i] * (Rs[i] - Ls[i]));
	}

	return ans;
}

int solve(){
	int ans = 0;

	memset(bs, -1, sizeof(bs));
	for(int i=0; i<W; i++){
		for(int j=0; j<W; j++)if(board[i][j]){
			bs[j] = i;
		}

		for(int j=0; j<W; j++){
			as[j] = i - bs[j];
		}

		ans = max(ans, calc());
	}

	return ans;
}

int main(){
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		printf("%d\n", solve());
	}

	return 0;
}