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; }