AWXCici
微光·浅月
采纳率100%
2020-08-01 12:44

一道C++题目,求正确代码!!!!

已采纳

黑格覆盖
时间限制: 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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • caozhy 回答这么多问题就耍赖把我的积分一笔勾销了 8月前
    #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;
    }
    
    

    https://blog.csdn.net/QXK_Jack/article/details/104125212

    点赞 评论 复制链接分享