[HNOI2003]激光炸弹

题解写重了 参考https://blog.nowcoder.net/n/62b1d5cfab0647cbae38a868fdd0e713
本题图片说明

按上图
设置M[i][j]记录以（1，1）为左上角端点 以(i,j)为右下角端点的矩形
大矩形=红色矩形+青色矩形-黑色重叠矩形+（i，j）点的数值
不难发现 按M[i][j]=M[i-1][j]+M[i][j-1]-M[i-1][j-1]+a[i][j]前缀即可
接下来直接枚举左上角(i,j)边长为k的正方形
M[i+k-1][j+k-1]-M[i+k-1][j-1]-M[i-1][j+k-1]+M[i-1][j-1]
注意细节 比如边界

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=5e3+7;
int  a[maxn][maxn];
int  M[maxn][maxn]={0};
int main()
{
  int  n,k;
  scanf("%d%d",&n,&k);
  memset(M,0,sizeof(M));
  int l=k,r=k;///这个很重要，最小的边界范围
  for (int i=0;i<n;++i)
  {
    int x,y,t;
    scanf("%d%d%d",&x,&y,&t);
    l=max(l,x+1);///寻找边界
    r=max(r,y+1);///寻找边界
    a[x+1][y+1]=t;
  }
  for (int i=1;i<=l;++i)
  {
    for (int j=1;j<=r;++j)
    {
        M[i][j]=M[i-1][j]+M[i][j-1]-M[i-1][j-1]+(a[i][j]);
    }
  }

  int  cnt=0;
  for (int i=1;i<=l-k+1;++i)///注意边界条件 只要l-i+1<=k即可
  {
    for (int j=1;j<=r-k+1;++j)///注意边界条件 只要r-i+1<=k即可
    {

      if (M[i+k-1][j+k-1]-M[i+k-1][j-1]-M[i-1][j+k-1]+M[i-1][j-1])///是i+k-1并非i+k 
    ///因为是从M[k]枚举到M[l]  
      {
        cnt=max(cnt,M[i+k-1][j+k-1]-M[i+k-1][j-1]-M[i-1][j+k-1]+M[i-1][j-1]);
      }
    }
  }
  printf("%d\n",cnt);
  return 0;
}