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输入 14 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2输出 115说明/提示样例解释该矩阵中的最大加权矩形为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 n120n120时运算量约2 × 10 8 2\times 10^82×108。代码实现#includebits/stdc.husingnamespacestd;intn,a[125][125],s[125][125],ans;// 全局变量自动初始化为0intmain(){cinn;// 读入矩阵大小for(inti1;in;i)// 读入矩阵下标从1开始方便前缀和for(intj1;jn;j)cina[i][j];// 计算二维前缀和 s[i][j] 表示从(1,1)到(i,j)的和for(inti1;in;i)for(intj1;jn;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(inti1;in;i)// 上边界 ifor(intji;jn;j)// 下边界 jfor(intk1;kn;k)// 左边界 kfor(intlk;ln;l){// 右边界 l// 利用二维前缀和公式计算矩形(i,k)-(j,l)的和intsums[j][l]-s[i-1][l]-s[j][k-1]s[i-1][k-1];if(sumans)anssum;// 更新最大值}coutansendl;// 输出结果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 n120n120时最坏约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 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}