2029:Get Many Persimmon Trees

keyword

BruteForce　尺取り法　C++

概要

2次元平面(100*100以下)が与えられて、各セルは0 or 1である。指定されたサイズの長方形で平面を切り取るとき、その長方形の中にある1の最大個数を求めよ。
サイズが固定だし、尺取り法(というか、区間をスライドさせる)で区間和を計算する。
オーダーが変わらないので2次元累積和で処理しても良い。

int board[102][102];
int accum[102][102];
int accum2[102][102];

int main(){
    int w, h, s, t, n;
    int i, j;
    while(n = readint(), n){
        w = readint();
        h = readint();
        REP(i,h)REP(j,w) board[i][j] = 0;
        REP(i,h-t)REP(j,w-s) accum[i][j] = 0;
        REP(i,h-t)REP(j,w-s) accum2[i][j] = 0;

        REP(i,n){
            int x = readint()-1, y = readint()-1;
            board[y][x] = 1;
        }

        s = readint();
        t = readint();

        REP(i,h){
            int sum = accumulate(board[i],board[i]+s,0);
            accum[i][0] = sum;
            REP(j,w-s){
                accum[i][j+1] = accum[i][j] - board[i][j] + board[i][j+s];
            }
        }

        REP(j,w-s+1){
            int sum = 0;
            REP(i,t) sum += accum[i][j];
            accum2[0][j] = sum;
            REP(i,h-t){
                accum2[i+1][j] = accum2[i][j] - accum[i][j] + accum[i+t][j];
            }
        }

        int ans = 0;
        REP(i,h-t+1)REP(j,w-s+1) ans = max(ans, accum2[i][j]);

        printf("%d\n",ans);
    }
    return 0;
}