【HNOI2003】激光炸彈

【HNOI2003】 激光炸彈

一道二維前綴和，是一道比較經典的純板子題目，針對這道題，我將再次進行二維前綴和的梳理

首先，要進行前綴和數組的推理得到d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1]；

但是這也可以用以下代碼實現：

for(int i=1;i<=maxn;i++)
	{
		for(int j=1;j<=maxn;j++)
		{
			a[i][j]+=a[i][j-1];
		}
	}
	for(int j=1;j<=maxn;j++)
	{
		for(int i=1;i<=maxn;i++)
		{
			a[i][j]+=a[i-1][j];
		}
	}

在求某一個區間值時，使用d[i][j]-d[i-1][j]-d[i][j-1]+d[i-1][j-1]

本道題就是一道板子，但是在處理循環的時候要避免以下問題：

例如：

const int maxn=5005;
int a[maxn][maxn];
for(int i=1;i<=maxn;i++)
{
    ...
}

會導致數據溢出，警鐘長鳴

接下來是代碼實現：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int a[maxn+1][maxn+1];
int m;
int n;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int xx,yy,w;
		cin>>xx>>yy>>w;
		a[xx+1][yy+1]+=w;
	}
	int ans=-114514;
	for(int i=1;i<=maxn;i++)
	{
		for(int j=1;j<=maxn;j++)
		{
			a[i][j]+=a[i][j-1];
		}
	}
	for(int j=1;j<=maxn;j++)
	{
		for(int i=1;i<=maxn;i++)
		{
			a[i][j]+=a[i-1][j];
		}
	}
	
	for(int i=m;i<=maxn;i++)
	{
		for(int j=m;j<=maxn;j++)
		{
			int op=a[i][j]-a[i-m][j]-a[i][j-m]+a[i-m][j-m];
			ans=max(ans,op);
		}
	}
	cout<<ans;
}