洛谷P2280 [HNOI2003] 激光炸弹 [前缀和]-白红宇

洛谷P2280 [HNOI2003] 激光炸弹 [前缀和]

阅读量：5173 次

发布时间：2019-06-13

本文共 1075 字，大约阅读时间需要 3 分钟。

题目描述

输入输出格式

输入格式：

输入文件名为input.txt

输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。

输出格式：

输出文件名为output.txt

输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。

输入输出样例

输入样例#1：

2 10 0 11 1 1

输出样例#1：

　　分析：也没什么好分析的，基本的前缀和，用下容斥原理，注意一下边界就可以了。

　　Code：（稍微有点乱，将就下吧）

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #define Fi(i,a,b) for(int i=a;i<=b;i++)using namespace std;const int N=5e3+7;int ans,n,m,a[N][N],maxx;int main(){ ios::sync_with_stdio(false); cin>>n>>m;int x,y,v; Fi(i,1,n){cin>>x>>y>>v;a[x][y]=v;maxx=max(maxx,max(x,y));} Fi(i,1,maxx)a[i][0]=a[i][0]+a[i-1][0],a[0][i]=a[0][i]+a[0][i-1]; Fi(i,1,maxx)Fi(j,1,maxx) {a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];} Fi(i,m,maxx)ans=max(ans,max(a[i][m-1]-a[i-m][m-1],a[m-1][i]-a[m-1][i-m])); Fi(i,m,maxx)Fi(j,m,maxx) {ans=max(ans,a[i][j]-a[i-m][j]-a[i][j-m]+a[i-m][j-m]);} cout<
              
               <<"\n";return 0;}