激光炸弹

[HNOI2003]激光炸弹

https://ac.nowcoder.com/acm/problem/20032

想看抄正确代码的请去其他题解
这道题我wa了三页
这道题考察的是二维前缀和,很简单,其他的知识点其他的题解都讲过了,这里不加赘述。
我想说的是关于数组越界的问题。在其他的题解中,对于坐标x,y都加1当成一种很自然的过程,然而并不是。我在群中询问其他同学,他们给我的答案是在求二位前缀和的过程中会数组越界,然而这不是我wa的原因。如果xy不+1,只会使得求二维前缀和变得稍许麻烦,但仍能过9个点。真正的问题是出在后续求最大值的部分。
以下是错误代码
#include <bits/stdc++.h>
using namespace std;
int a[5001][5001] = {0};
int main()
{
int n, r;
cin >> n >> r;
int xx = r, yy = r;
while (n--)
{
int x, y, v;

    cin >> x >> y >> v;
    a[x][y] = v;
    xx = max(xx, x);
    yy = max(yy, y);
}
for (int i = 0; i <= xx; i++)
    for (int j = 1; j <= yy; j++)
        a[i][j] += a[i][j - 1]; //行的前缀和

for (int j = 0; j <= yy; j++)
    for (int i = 1; i <= xx; i++)
        a[i][j] += a[i - 1][j];

int maxx = 0;
for (int i = r; i <= xx; i++)//因为我xy没有+1,所以这里ij的初始值应该从r-1开始
    for (int j = r; j <= yy; j++)//然而从r-1开始会造成数组越界,这就是问题所在
    {
        maxx = max(maxx, a[i - r][j - r] - a[i][j - r] - a[i - r][j] + a[i][j]);
    }
cout << maxx;
return 0;

}
为了找到这个问题我打了一堆表,在这里感谢雨巨的帮助
最后附一组我gg的数据吧
输入:
2 1
0 0 1
0 1 1
正确输出 :
1

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务