激光炸弹（二维前缀和）

-（图画的有点丑意思意思就行了）学习二维前缀和首先要了解的是二维前缀和是哪些的和---（在下图中A点的前缀和是红色部分，B点的前缀和是红色加绿色部分（至于是哪一部分绿色自己想想也知道），C点的同B点，D点的是红色加所有绿色部分再加白色部分,这里可以这样理解sum[i][j]的值是a[i][j]左上这整个大矩形的值的和（类似于面积）

• 二维前缀和：(sum[i][j]是a[i][j]的前缀和)

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

• 至于这个公式如何来的：我们把D点的前缀和看成sum[i][j],D点在a[]数列中的值是a[i][j],那么sum[i][j]就是a[]左上的和，同理A,B,C也分别是他们所在点a[i-1][j-1],a[i][j-1],a[i-1][j]左上矩形内的值的和， 则D点的sum[i][j]就等于白色矩形加两个绿色矩形再加红色矩形，而除了白色矩形就是a[i][j]，其他的和就是两个绿色的矩形加红色的矩形（等于sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]）(因为sum[i-1][j]+sum[i][j-1]中加了两次红***域)所以sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
  
• 那么怎么求任意区域内的值呢？
• (依据面积加减)下图绿颜域的值等于(sum[x2][y2]减去红颜域的值)，而红颜***域的的值为sum[x2][y1]+sum[x1][y2]-sum[x1][y1] (和求前缀和求解差不多);
  
  这是个前缀和的裸题：https://ac.nowcoder.com/acm/problem/20032
• 先求前缀和然后按照每一个可能的点暴力遍历一遍求出遍历的每个区域内的值取其中最大值就可以愉快的ac了！！！

  #include<bits/stdc++.h>
  using namespace std;
  #define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)//使cout和cin更快读入数据
  const int maxn = 5e3 + 50;
  const int inf = 0x3f3f3f3f;
  const int mod = 1e9 + 7;
  int sum[maxn][maxn];
  int n,r;
  int main()
  {
     IOS;
     cin>>n>>r;
     int a=r,b=r;
     for(int i=1;i<=n;i++)
     {
         int x,y,v;
         cin>>x>>y>>v;
         x++,y++;//为了使下，x,y下标从1开始
         sum[x][y]+=v;
         a=max(a,x);//找最长的行
         b=max(b,y);//找最长的列
     }
     for(int i=1;i<=a;i++)
     {
         for(int j=1;j<=b;j++)
         {
             sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];//计算前缀和  sum[i][j]在没求和之前已经等于a[i][j]了
         }
     }
     int ans=0;
     for(int i=r;i<=a;i++)
     {
         for(int j=r;j<=b;j++)
         {
             ans=max(ans,sum[i][j]-sum[i-r][j]-sum[i][j-r]+sum[i-r][j-r]);//求每个r*r区域内的值然后取最大值
         }
     }
     cout<<ans<<endl;
     return 0;
  }
  
  

```
//第一篇博客2020.05.21