寒假训练热身赛前后缀----激光炸弹

系列文章目录 寒假训练热身赛

前后缀----激光炸弹

文章目录

• 系列文章目录
• 一、题目
• 二、代码

---

前言 一、题目

二、代码

代码如下（示例）：

#include  
#include  
using namespace std; 
int a[5005][5005]; 
int main() 
{ 
     int x,y; 
     int n,r,xi,yi,vi,i,j,sum=0;
     cin >> n >> r; 
     r=min(r,5001);//因为炸5000*5000范围，r太大无用，因为从（x，y）开始方便计算
     x=y=r;//确定炸的范围
    while(n--)
 {
    cin >> xi >> yi >> vi; 
   xi++,yi++; 
   a[xi][yi]+=vi;

     x=max(x,xi); 
    y=max(y,yi);//确定右下角（x，y）；当r不足以覆盖全图时
 } 
     for(i=1;i<=x;i++) 
       for(j=1;j<=y;j++)
 { 
      a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];//将原来的数组转化为前缀和数组//预处理状态转移方程为（Dp[i][j]=Dp[i-1][j]+Dp[i][j-1]-Dp[i-1][j-1]+map[i][j])
 } 
   for(i=r;i<=x;i++)
     for(j=r;j<=y;j++) 
{                                                                                                                            
     sum=max(sum,a[i][j]-a[i-r][j]-a[i][j-r]+a[i-r][j-r]);//i,j表示的是矩形的右下角，i-r，j-r表示的是左上角
} 
      cout <