黑格覆盖
时间限制: 1 Sec 内存限制: 128 MB
题目描述
在一张由 M*N 个小正方形格子组成的矩形纸张上，有 k 个格子被涂成了黑色。给你一 张由 m*n 个同样小正方形组成的矩形卡片，请问该卡片最多能一次性覆盖多少个黑格子？
输入
输入共 k+1 行：
第 1 行：为 5 个整数 M、N、m、n、k，其含义如题目所述。
接下来 k 行：每行 2 个整数，分别表示被涂成黑色的格子的行、列坐标。
输出
输出共 1 行，1 个整数，表示卡片一次性最多能覆盖的黑格子数。
样例输入
3 5 2 2 3
1 1
2 2
3 5
样例输出
2
#include<bits/stdc++.h>
using namespace std;
int A[1010][1010];
int main()
{
int M,N,m,n,k;
scanf("%d %d %d %d %d",&M,&N,&m,&n,&k);
for(int i=1;i<=k;i++)
{
int a,b;
scanf("%d %d",&a,&b);
A[a][b]=1;
}
for(int i=1;i<=M;i++)
{
for(int j=1;j<=N;j++)
A[i][j]=A[i][j-1]+A[i-1][j]-A[i-1][j-1]+A[i][j];
}
int maxn=0;
if(m>M) m=M;
if(n>N) n=N;
for(int i=M;i>=m;i--)
{
for(int j=N;j>=n;j--)
{
int num=A[i][j]+A[i-m][j-n]-A[i-m][j]-A[i][j-n];
maxn=max(maxn,num);
}
}
if(m>N) m=N;
if(n>M) n=M;
for(int i=M;i>=n;i--)
{
for(int j=N;j>=m;j--)
{
int num=A[i][j]+A[i-n][j-m]-A[i-n][j]-A[i][j-m];
maxn=max(maxn,num);
}
}
printf("%d",maxn);
return 0;
}