HNOI2003激光炸弹问题（二维前缀和的应用）难度：中等

HNOI2003 激光炸弹问题

输出示例：

2 1 0 0 1 1 1 1 

输入示例：

1 

这是一道典型的二维前缀和应用题目。通过构建前缀和矩阵，可以高效地计算任意子矩阵的和。具体步骤如下：

• 读取输入数据，初始化前缀和矩阵。
• 计算前缀和矩阵，确保每个元素表示从(0,0)到当前坐标的矩形区域内的总和。
• 遍历所有可能的子矩阵，找到最大值。

以下是详细的代码实现：

#include  #include  #include  using namespace std; typedef int ll; const ll N = 5007; ll n, m; ll b[N][N]; ll x, y, v, ans; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%d%d%d", &x, &y, &v); b[x + 1][y + 1] = v; } for (int i = 1; i <= 5001; ++i) { for (int j = 1; j <= 5001; ++j) { b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j]; } } for (int i = 0; i <= 5000 - m; ++i) { for (int j = 0; j <= 5000 - m; ++j) { ans = max(ans, b[i + m][j + m] - b[i + m][j] - b[i][j + m] + b[i][j]); } } printf("%d\n", ans); return 0; } 

如果有任何疑问，欢迎在评论区留言。喜欢的话，别忘了点个赞哦！