nered.cpp

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

bool maximize(int &a, int b){ if (a<b) a=b; else return false; return true; }

int n, m;

int answer=0;

int a[123][123];

int sum(int x, int y, int xx, int yy){

    return a[xx][yy] - a[x-1][yy] - a[xx][y-1] + a[x-1][y-1];

}

void attempt(int W, int H){

    int i, j;

    for (int i=1; i+W-1<=n; i++)

    for (int j=1; j+H-1<=n; j++)

    maximize(answer, sum(i,j,i+W-1,j+H-1));

}

main(){

    int i, j, p, q, W;

    scanf("%d%d", &n, &m);

    for (i=1; i<=m; i++){

        scanf("%d%d", &p, &q);

        a[p][q]=1;

    }

    for (i=1; i<=n; i++)

    for (j=1; j<=n; j++)

    a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];

    for (W=1; W<=m && W<=n; W++)

    if (m%W==0 && m/W<=n)

    attempt(W, m/W);

    printf("%d\n", m-answer);

}

Nhận xét