原题链接:https://www.luogu.com.cn/problem/P2004
题意解读:在一个n*m的矩阵中,找到边长为c的正方形,使得正方形范围内的数之和最大,输出正方形的左上角坐标。
解题思路:
二维前缀和的简单应用
第一步:计算二维前缀和
第二步:枚举边长为c的正方形左上角,计算正方形区域的数之和,更新答案
第三步:输出答案
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N][N], s[N][N];
int n, m, c;
int ansx, ansy, maxs = -1e9;
int main()
{
cin >> n >> m >> c;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
//计算二维前缀和
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}
//枚举正方形的左上角
for(int x1 = 1; x1 <= n - c + 1; x1++)
{
for(int y1 = 1; y1 <= m - c + 1; y1++)
{
int x2 = x1 + c - 1;
int y2 = y1 + c - 1;
//计算正方形范围数的和
int sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
if(sum > maxs)
{
maxs = sum;
ansx = x1;
ansy = y1;
}
}
}
cout << ansx << " " << ansy;
return 0;
}
标签:前缀,P2004,int,洛谷题,差分,正方形,maxs,x1 From: https://www.cnblogs.com/jcwy/p/18330287