1218: [HNOI2003]激光炸弹

题解：

　　一道经典题目啊...

　　为了更好的操作...把整个坐标系向右上角移动，从(1,1)开始

　　那么f[i][j]统计一下以(i,j)作为右上角，以(1,1)作为左下角所组成的矩阵里面的价值和

　　不难发现，爆炸范围为R*R，且刚好在边上的点不会被摧毁，那么有效矩阵的四条边上肯定就只有R个点

　　那么ans=max(ans,f[i][j]+f[i-r][j-r]-f[i][j-r]-f[i-r][j]);

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int f[][];

 int main()

 {

     memset(f,,sizeof(f));

     int n,r,x,y,v;scanf("%d%d",&n,&r);

     for(int i=;i<=n;i++)scanf("%d%d%d",&x,&y,&v),f[x+][y+]+=v;

     for(int i=;i<=;i++)

         for(int j=;j<=;j++)f[i][j]+=f[i-][j];

     for(int i=;i<=;i++)

         for(int j=;j<=;j++)f[i][j]+=f[i][j-];

     int ans=;

     for(int i=r;i<=;i++)for(int j=r;j<=;j++)

         ans=max(ans,f[i][j]+f[i-r][j-r]-f[i][j-r]-f[i-r][j]);

     printf("%d\n",ans);

     return ;

 }

巴特西

bzoj1218: [HNOI2003]激光炸弹（DP二维前缀和）

1218: [HNOI2003]激光炸弹

最新文章

热门文章