【蓝桥杯题解】激光炸弹 (二维前缀和)
激光炸弹
思路与题目解读
这个题坑巨多，那个R的范围远大于区间的范围，所以R最多只能取到5001,否则就会数组越界SF，思路就是二维的前缀和.
C++代码
题解好多代码 和y总的代码现在都用不了,这是最新的
#include <iostream>
using namespace std;
const int N = 5010;
int s[N][N];//c++ 大数组开全局
int main () {
int N,R;// C++重名优先使用局部变量
cin >> N >> R;
R = min (R, 5001);
int n = R,m = R;
for (int i = 0,x,y,w; i < N; i ++) {
cin >> x >> y >> w;
s[x+1][y+1] += w;
//映射到1 ,为了满足题意不考虑边界
n = max(n, x+1),m= max(m, y+1);//更新最大边界
}
for(int i = 1;i <= n;i ++) {
for(int j = 1;j <= m; j ++) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
}
}
int ans = 0;
for (int i = R; i <= n; i ++) {
for (int j = R; j <= m; j ++) {
ans = max (ans,s[i][j] - s[i - R][j] - s[i][j - R] + s[i -R][j - R]);
}
}
cout << ans << endl;
return 0;
}
上一篇：
通过多线程提高代码的执行效率例子