题目链接:https://ac.nowcoder.com/acm/contest/999/A
题意:给定一个矩阵上有N个点,然后给出每个点的坐标与其权值,问一个边长为r的正方形框最大程度可以框住的范围内所有点权值之和的最大值。
知识点:二维前缀和
介绍:
- 一维前缀和就是一种思想,直接贴代码
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]
- 二维前缀和就是相当于拓展到了矩阵上,即点(x,y)的左上角元素之和就是s[x][y]。
- 求法:我们实际要求的就是红色范围内的值,可以通过容斥原理来求得,即红 = 总-蓝白-黑白+白。
- 代码就是
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]
顺带介绍一下差分
- 差分实际上经常与前缀和一起出现,因为差分与前缀和是互逆的运算
- 假设有数组a,b,c,其中,a是原数组,b是前缀和数组,c是差分数组
- 那么b是a的前缀和、a是c的前缀和。
- 即a[i] = c[1] + …… + c[i];
- 用一个函数实现该操作
//一维差分
void insert(int l, int r, int w)//l表示插入区间的左端点,r表示右端点,w表示值 { c[l] += w; c[r + 1] -= w; }
//二维差分
void insert(int x1, int y1, int x2, int y2, int c) { b[x1][y1] += c; b[x1][y2 + 1] -= c; b[x2 + 1][y1] -= c; b[x2 + 1][y2 + 1] += c; }
- 然后是本题代码
-
#include <bits/stdc++.h> using namespace std; const int maxn = 5010; int g[maxn][maxn]; int main() { ios::sync_with_stdio(false); int n, r; cin >> n >> r; int N = r, M = r;//用此判断边界,因为有可能最大值都没有r大,我们就先初始化为r for(int i = 1, x, y, w; i <= n; i++) { cin >> x >> y >> w; x++; y++;//习惯用1开始的下标,使用前缀和会更顺手 g[x][y] += w; N = max(N, x); M = max(M,y); } for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) g[i][j] = g[i][j] + g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];//在这里没有多开数组,直接用g表示前缀和 int res = 0; for(int i = r; i <= N; i++) for(int j = r; j <= M; j++) res = max(res, g[i][j] - g[i - r][j] - g[i][j - r] + g[i - r][j - r]); cout << res << endl; return 0; }
原文链接: https://www.cnblogs.com/ACM-Epoch/p/13354824.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/369379
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!