OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HNOI2003】激光炸弹

【题目描述】

一种新型的激光炸弹,可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(n<=10000)个目标,用整数xi,yi(0<=xi,yi<=5000), 表示目标在地图上的位置,每个目标都有一个价值0< vi< 100 。激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆破范围,即那个边长为R的正方形的边必须和x,y轴平行。若目标位于爆破正方形的边上,该目标将不会被摧毁。
现在你的任务是计算一颗炸弹最多能炸掉地图上总价值为多少的目标。

【输入】

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

【输出】

有一个正整数,表示一颗炸弹最多能炸掉地图上总价值为多少的目标(结果不会超过32767)。

【输入样例】

2 1

0 0 1

1 1 1

【输出样例】

1

【题解】

用类似前缀和的东西预处理,即f[i][j]表示坐标在(0~i,0~j)之中的所有目标的价值和,f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1],以后查询任意子矩阵时,O(1)就可以得到结果(不知道这个有没有标准的名称,我自己叫的时前缀矩阵o(╯□╰)o)。

然后枚举正方形,找出一个价值和最大的即可。由于是正方形,确定了左下角也就确定了查询范围,所以O(n^2)便可以完成。

正解应该是二维线段树/x轴线段树+y轴线段树/二维树状数组这样的吧0.0但是不涉及修改,总感觉这样不划算o(╯□╰)o

【代码】

预处理和枚举都是O(n^2),内存开销大,所以在学校的OJ怎么都过不了(赌五毛是学校开错内存限制了。。)

http://paste.ubuntu.com/8110321/

评论

© OI技术宅 | Powered by LOFTER