csp信奥赛C++高频考点专项训练之前缀和差分 --【二维前缀和】：最大加权矩形
csp信奥赛C++高频考点专项训练之前缀和&差分 --【二维前缀和】：最大加权矩形
题目描述
为了更好地备战 NOIP 2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为：我们不光需要机房，我们还需要运动。于是她们决定找校长申请一块电脑组的课余运动场地。听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并告诉她们，她们能获得的运动场地的面积就是她们能找到的这个最大的数字。
校长给她们一个大小为n × n n\times nn×n的矩阵，矩阵中的每一个元素都有一个整数权值，要她们求出该矩阵中的最大加权矩形（即从中找一大小不限的矩形，使其中包含的所有元素的权值和最大）中所有元素的权值和，且矩阵中每个元素的权值均在区间[ − 127 , 127 ] [-127,127][−127,127]内。
几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH,TZY 小朋友帮忙计算，但是遗憾的是，他们的答案都不一样。涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？
输入格式
第一行包含一个正整数n nn。
接下来n nn行每行包含n nn个整数，表示给定的矩阵。
输出格式
输出一行一个整数，表示该矩阵的最大加权矩形中所有元素的权值和。
输入输出样例 1
输入 1
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2输出 1
15说明/提示
样例解释
该矩阵中的最大加权矩形为
9 2 -4 1 -1 8它们的和为15 1515。
数据范围
对于100 % 100\%100%的数据，1 ≤ n ≤ 120 1 \leq n\le 1201≤n≤120。
思路分析
最大加权矩形问题可以直接利用二维前缀和枚举所有可能的矩形。
- 预处理前缀和数组
s[i][j]表示从(1,1)到(i,j)的矩阵元素和。 - 枚举矩形的左上角
(x1,y1)和右下角(x2,y2)，通过前缀和公式O ( 1 ) O(1)O(1)计算出该矩形内所有元素的和：sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]。 - 维护全局最大值
ans，最终输出。
时间复杂度O ( n 4 ) O(n^4)O(n4)，n = 120 n=120n=120时运算量约2 × 10 8 2\times 10^82×108。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,a[125][125],s[125][125],ans;// 全局变量自动初始化为0intmain(){cin>>n;// 读入矩阵大小for(inti=1;i<=n;i++)// 读入矩阵，下标从1开始方便前缀和for(intj=1;j<=n;j++)cin>>a[i][j];// 计算二维前缀和 s[i][j] 表示从(1,1)到(i,j)的和for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];ans=-2e9;// 初始化为极小值（因为元素可能全负）// 枚举矩形左上角 (i,k) 和右下角 (j,l)for(inti=1;i<=n;i++)// 上边界 ifor(intj=i;j<=n;j++)// 下边界 jfor(intk=1;k<=n;k++)// 左边界 kfor(intl=k;l<=n;l++){// 右边界 l// 利用二维前缀和公式计算矩形(i,k)-(j,l)的和intsum=s[j][l]-s[i-1][l]-s[j][k-1]+s[i-1][k-1];if(sum>ans)ans=sum;// 更新最大值}cout<<ans<<endl;// 输出结果return0;}功能分析
- 输入：正整数n nn和一个n × n n\times nn×n的整数矩阵（元素范围− 127 -127−127到127 127127）。
- 处理：
- 构建二维前缀和数组，使任意子矩阵的和可在O ( 1 ) O(1)O(1)时间内计算。
- 使用四重循环枚举所有可能的子矩形（左上角和右下角坐标）。
- 每次通过前缀和公式快速计算矩形和，并更新全局最大值。
- 输出：一个整数，即所有子矩形中元素和的最大值。
- 正确性：枚举了所有O ( n 4 ) O(n^4)O(n4)个矩形，每个矩形的和都被准确计算，因此一定能找到最大加权矩形。
- 性能：时间复杂度O ( n 4 ) O(n^4)O(n4)，n = 120 n=120n=120时最坏约2.07 × 10 8 2.07\times10^82.07×108次循环，每次循环仅做几次整数运算。空间复杂度O ( n 2 ) O(n^2)O(n2)，满足要求。
【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}