激光炸弹：最大价值目标摧毁策略

"激光炸弹.md" 本题是一个典型的二维前缀和问题，涉及到了数据结构和算法中的数组处理。题目描述了一个激光炸弹可以摧毁R×R范围内所有目标的场景，要求计算出最多能炸掉多少价值的目标。目标的位置用坐标(Xi, Yi)表示，价值用Wi表示，且可能存在相同位置的目标。 首先，我们需要了解输入格式： - 第一行输入正整数N（目标数量）和R（激光炸弹的边长）。 - 接下来的N行，每行包含三个整数Xi, Yi, Wi，分别代表目标的x坐标、y坐标和价值。 接着，我们需要处理这些数据： - 使用二维数组s[N][N]来存储每个位置上的目标总价值。由于坐标范围为0到5000，因此数组的大小设置为5001×5001，以确保覆盖所有可能的位置。 - 当读入一个目标时，将其价值累加到对应坐标的位置上。注意，由于数组索引从1开始，所以实际坐标比输入坐标大1。 - 在累加过程中，使用“+=”操作符，而非“=”。这是因为同一位置可能有多个目标，所以需要累加价值，而不是覆盖。 然后，为了计算最大价值，我们需要遍历二维数组s，利用前缀和的性质来快速得到每个R×R正方形区域内的总价值。具体步骤如下： - 对于每个可能的左上角位置(i, j)，我们需要计算出以(i, j)为左上角，边长为R的正方形内所有目标的总价值。 - 这可以通过计算s[i+r][j+r] - s[i+r][j-1] - s[i-1][j+r] + s[i-1][j-1]得出，这四个值分别代表了右下角、右上角、左下角和左上角的前缀和，通过它们的差值得到目标区域的总价值。 最后，遍历整个二维数组，找出所有可能的左上角位置，记录下最大价值，并在所有遍历结束后输出这个最大值。 给出的参考答案使用C++编写，包含了基本的输入输出处理、二维前缀和的计算以及遍历寻找最大价值的过程。在实际编程中，需要注意边界条件的处理和数组大小的设定，以避免溢出或无效计算。