c++写法分析

[toc]三、前缀和34、要快速算正方形总和如果不用 s 数组你算一个 C×C 正方形要一个个加太慢了会超时。所以我们再开一个仓库名字叫 s专门存前缀和让计算一秒完成。cpp运行int s[MAX][MAX];s 前缀和数组作用1 秒算出任意正方形的和35、for(int i1;iN;i){for(int j1;jM;j){s[i][j] a[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1];}}它是干嘛的它是一个 “快速求和工具”不用一个个加1 秒算出任意矩形的和。为什么要它如果你不用它算一个 2×2 正方形要加 4 次算 1000×1000 地图电脑会累死、超时。人话解释a[i][j] 当前格子的值s[i][j] 从左上角 (1,1) 到 (i,j) 的所有数字总和后面那一串是固定公式背下来就行 你不用懂为什么这么算只要知道算完 s 数组就能快速求正方形和36、for(int i1; iN-C1; i){ for(int j1; jM-C1; j){遍历所有可以放正方形左上角的位置i 行j 列N-C1 保证正方形不会超出地图int x2 i C - 1;int y2 j C - 1;超级简单左上角是 (i,j)正方形边长是 C那右下角自然是行i C - 1列j C - 1最关键一句计算正方形总和cpp运行int sum s[x2][y2] - s[i-1][y2] - s[x2][j-1] s[i-1][j-1];//人话翻译用前缀和 一秒算出 C×C 正方形的和//遍历所有正方形找最大和固定公式这也是固定公式直接背36、权值 这个格子的分数 / 价值那 “权值和” 是什么就是把正方形里的数字加起来 权值和比如你框一个 2×2 的正方形9 2-4 1权值和 9 2 (-4) 1 837、2. 四个循环是什么cpp运行for(int top1;topn;top){ // 上边界 for(int bottomtop;bottomn;bottom){ // 下边界 for(int left1;leftn;left){ // 左边界 for(int rightleft;rightn;right){ // 右边界大白话翻译top 矩形最上面一行bottom 矩形最下面一行left 矩形最左边一列right 矩形最右边一列四个循环合起来就是遍历地图里所有可能的矩形不管是大矩形、小矩形、正方形、长方形全部遍历一遍3. 这一行最关键计算矩形的和cpp运行int sum s[bottom][right] - s[top-1][right] - s[bottom][left-1] s[top-1][left-1];大白话用前缀和一秒算出当前这个矩形里所有数字的总和权值和你不用懂原理只需要记住这就是算任意矩形和的万能公式