【二维前缀和】洛谷_2280 激光炸弹

本文主要是介绍【二维前缀和】洛谷_2280 激光炸弹，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个矩阵，里面每个格子里面有一个价值，我们现在有一个$r*r$的框，求用这个框框住的子矩阵里的价值总和最大是多少。

思路

我们可以用二维前缀和记录一下每个点为右下角的子矩阵的价值总和，然后枚举一下就好了。

代码

#include<cstdio>
#define max(a,b) a>b?a:b
int n,r,s[5003][5003],a,b,c,ans;//这里用2个数组会爆
int main()
{scanf("%d%d",&n,&r);for (int i=1;i<=n;i++){scanf("%d%d%d",&a,&b,&c);s[a+1][b+1]=c;}for (int i=1;i<=5001;i++)for (int j=1;j<=5001;j++)s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];//二维前缀和for (int i=r;i<=5001;i++)for (int j=r;j<=5001;j++)ans=max(s[i][j]-s[i][j-r]-s[i-r][j]+s[i-r][j-r],ans);//枚举答案printf("%d",ans);
}

这篇关于【二维前缀和】洛谷_2280 激光炸弹的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---