一道很好的二维前缀和模板题。

什么是二维前缀和？

从这张图可以看出前缀和的求法:

Map[i][j]=Map[i-1][j]+Map[i][j-1]-Map[i-1][j-1]+Map[i][j];

这道题的代码:

#include
    
     using namespace std;const int MAXN=5000+10;int n,r;int Map[MAXN][MAXN];//数组开的下inline int read(){    int tot=0;    char c=getchar();    while(c<'0'||c>'9')        c=getchar();    while(c>='0'&&c<='9')    {        tot=tot*10+c-'0';        c=getchar();    }    return tot;}int main(){    int x,y,v;    n=read();r=read();    for(int i=1;i<=n;i++)    {        x=read();y=read();v=read();        Map[x+1][y+1]=v;    }    for(int i=1;i<=5000;i++)//因为地图最大是5000*5000的        for(int j=1;j<=5000;j++)            Map[i][j]=Map[i-1][j]+Map[i][j-1]-Map[i-1][j-1]+Map[i][j];//求出这张图的二维前缀和    int ans=0;    for(int i=0;i<=5000-r;i++)        for(int j=0;j<=5000-r;j++)//放置炸弹的范围，要减去边长，否则肯定不是最优的            ans=max(ans,Map[i+r][j+r]-Map[i][j+r]-Map[i+r][j]+Map[i][j]);//先找到爆炸范围中的总价值，再取最大值    cout<
     
      <