python 网站开发怎么部署,物流网络图,wordpress简体中文版下载地址,珠海绿网科技有限公司题目介绍#xff1a;
题目链接#xff1a;【模板】二维前缀和_牛客题霸_牛客网 先举两个简单的例子#xff0c;来帮大家理解题目#xff0c;注意理解二维前缀和要先要一维前缀和的基础#xff0c;不了解的可以看我上一篇博客。
若x11#xff0c;y11, x23, y2 3,这是要…题目介绍
题目链接【模板】二维前缀和_牛客题霸_牛客网 先举两个简单的例子来帮大家理解题目注意理解二维前缀和要先要一维前缀和的基础不了解的可以看我上一篇博客。
若x11y11, x23, y2 3,这是要查询下面这片区域的和 若x13y13, x26, y2 5,这是要查询下面这片区域的和 算法原理
暴力解法很简单直接死算必定超时所以还是要构建我们的前缀和数组dpdp数组的构建方法绝不能是每个数据都死死的去加一遍不然和暴力解法没什么区别也会超时。
构建二维前缀和数组重点
如何更高效地构造二维前缀和数组呢之前构建一维前缀和数组时我们可以很快用肉眼看出规律但二维前缀和数组的构建方法需要我们画图寻找新方法 我们将原数组划分为4个部分此时我们要求dp[i][j]的大小其实就是整个图形的面积也就是ABCDA很好表示Adp[i-1][j-1],D就一个元素也很好表示Darr[i][j] 可是B和C却不好表示但是AB和AC我们却很好表示ABdp[i-1][j],ACdp[i][j-1],如图 所以我们就得出了我们的重要结论
dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]arr[i][j]
通过这个表达式我们就能构建出二维前缀和数组了。
使用二维前缀和数组
我们已经构建出了二维前缀和数组那么如何使用它呢如图我们输入x1y1x2y2后 还是一样先划分为A,B,C,D 4个区域 此时D为我们所求还是根据刚才的思路来换算
DABCD-ABC)
ABCDdp[x2][y2]
B和C单独在一块不好求就转化成AB和AC如
DABCD-ABC)ABCD-(AB)-(AC)Adp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]
所以的出重要结论
Ddp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1] 最后我们只需将x1y1x2y2代入上式中就可以求得答案了。
代码实现
C
#include iostream
#includevector
using namespace std;int main() {//读入数据int n 0,m0,q0;cin n m q;vectorvectorint arr(n1, vectorint(m1));int i1;for(i1;in;i){int j1;for(j1;jm;j){cin arr[i][j];}}//处理dp数组vectorvectorlong long dp(n1, vectorlong long(m1));for(i1;in;i){int j1;for(j1;jm;j){dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]arr[i][j];}}//开始使用dp数组进行q次查询while(q--){int x10,y10,x20,y20;cin x1 y1 x2 y2;cout dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1] endl;}return 0;
}
