c++111111111111111111111111111111111111

Question

问题 D: 2018-黑格覆盖（cover）
时间限制: 1 Sec 内存限制: 128 MB
提交: 118 解决: 17
[提交] [状态] [讨论版] [命题人:admin]
题目描述
在一张由 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

提示
【样例说明】 根据样例数据所得到的涂完黑格的矩形和用于覆盖的矩形如下图所示：

【数据范围】 对于 40%的数据：m=n； 对于 100%的数据：M、N、m、n、k 均小于等于 1000，所有黑格不重复出现
我的代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,f,g,k;
int a[1005][1005],b[1005][1005];
int z,d,s;
int main(){
    cin>>n>>m>>f>>g>>k;
    for(int i=1;i<=k;i++){
        cin>>z>>d;
        a[z][d]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
        b[i][j]=b[i][j-1]+b[i-1][j]+a[i][j]-b[i-1][j-1];
    }for(int i=f;i<=n;i++){
        for(int j=g;j<=m;j++){
        int tmp=b[i][j]-b[i-f][j]-b[i][j-g]+b[i-f][j-g];
        s=max(s,tmp); 
        }
    }cout<<s;
    return 0;
}

谭，帮帮我

Answer 1

//程序名:新的C++程序
//作者: 
 
#include<iostream>
#include<fstream>
#include<algorithm>
 
using namespace std;
int b[1145][1145],b_y[1145][1145];
int b_x[1145][1145]; 
int ma,q,w,x,y,shu;
int main()
{cin>>q>>w>>x>>y>>shu;
    for(int i=1;i<=shu;i++){
         int x_,y_;
         cin>>y_>>x_;
         b[y_][x_]=1;
    }
    for(int i=1;i<=q;i++){
        for(int z=1;z<=w;z++){
            if(z-1>=1)
                b[i][z]=b[i][z]+b[i][z-1];
             
            if(i-1>=1)
                b_y[i][z]=b_y[i-1][z];
            if(z-y>=1)
                b_y[i][z]=b_y[i][z]+(b[i][z]-b[i][z-y]);
            else
                b_y[i][z]=b_y[i][z]+b[i][z];
             
            if(i-x>=1)
                ma=max(ma,(b_y[i][z]-b_y[i-x][z]));
            else
                ma=max(ma,b_y[i][z]);
             
        }
    }
     
    for(int i=1;i<=q;i++){
        for(int z=1;z<=w;z++){   
            if(i-1>=1)
                b_x[i][z]=b_x[i-1][z];
            if(z-x>=1)
                b_x[i][z]=b_x[i][z]+(b[i][z]-b[i][z-x]);
            else
                b_x[i][z]=b_x[i][z]+b[i][z];
             
            if(i-y>=1)
                ma=max(ma,(b_x[i][z]-b_x[i-y][z]));
            else
                ma=max(ma,b_x[i][z]);
             
        }
    }
 
    cout<<ma;
 
    return 0;
}