ACwing99 激光炸弹二维前缀和

2021-01-28 21:15

阅读：1394

标签：typedef tar class cpp wing ref href long can

网址：https://www.acwing.com/problem/content/101/

题意：

给出一个矩阵，求边长为$R$的正方形子矩阵和的最大值。

题解：

求二维前缀和然后枚举左上角点即可。

二维前缀和求法：$S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+a[i][j]$。其中因为$S[i-1][j-1]$加了两次，所以需要减去一次。

$O(1)$求子矩阵和：$sum=S[i][j]-S[i-k][j]-S[i][j-l]+S[i-k][j-l]$。

AC代码：

#include 
using namespace std;
typedef long long ll;
const int MAXN = 5005;
int s[MAXN][MAXN];
int main()
{
	int n, r, a, b, v;
	scanf("%d%d", &n, &r);
	for (int i = 0; i

ACwing99 激光炸弹二维前缀和

标签：typedef tar class cpp wing ref href long can

原文地址：https://www.cnblogs.com/Aya-Uchida/p/11873891.html

上一篇：Windows网络命令的相关指令(1)

下一篇：AcWing 9. 分组背包问题

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：ACwing99 激光炸弹二维前缀和
文章链接：http://soscw.com/index.php/essay/48405.html

亲，登录后才可以留言！

ACwing99 激光炸弹二维前缀和

题意：

题解：

评论

热门文章

推荐文章

最新文章

置顶文章

ACwing99 激光炸弹 二维前缀和

题意：

题解：

评论

热门文章

推荐文章

最新文章

置顶文章

ACwing99 激光炸弹二维前缀和