AcWing 99 激光炸弹【二维前缀和】

tech2022-08-07  1

题目链接

题目描述


题解:

做一道题,复习一下二维前缀和,设数组 d p [ i ] [ j ] dp[i][j] dp[i][j],表示第 i 行第 j 列格子左上部分所有元素的和(包括自己),

初始化递推公式:

d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] − d p [ i − 1 ] [ j − 1 ] + w [ i ] [ j ] dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + w[i][j] dp[i][j]=dp[i1][j]+dp[i][j1]dp[i1][j1]+w[i][j]

查询子区间和(区间左上角格子为( x 1 , y 1 x_{1}, y_{1} x1,y1),右下角格子坐标为( x 2 , y 2 x_{2}, y_{2} x2,y2)):

a n s = d p [ x 2 ] [ y 2 ] − d p [ x 1 − 1 ] [ y 2 ] − d p [ x 2 ] [ y 1 − 1 ] + d p [ x 1 − 1 ] [ y 1 − 1 ] ans = dp[x_{2}][y_{2}] - dp[x_{1} - 1][y_{2}] - dp[x_{2}][y_{1} - 1] + dp[x_{1} - 1][y_{1} - 1] ans=dp[x2][y2]dp[x11][y2]dp[x2][y11]+dp[x11][y11]

回归本题:

初始化前缀和,然后枚举边长为r的子区间即可,注意根据读入数据最大值确定x和y边界大小。


AC代码

#include <iostream> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <deque> #include <list> #include <iomanip> #include <algorithm> #include <fstream> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> //#pragma GCC optimize(2) using namespace std; typedef long long ll; //cout << fixed << setprecision(2); //cout << setw(2); const int N = 5e3 + 5, M = 1e9 + 7; int dp[N][N]; int main() { //freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, r; cin >> n >> r; int a = r, b = r, x, y, w; for (int i = 0; i < n; i++) { cin >> x >> y >> w; x++, y++; if (x > a) a = x; if (y > b) b = y; dp[x][y] += w; } for (int i = 1; i <= a; i++) { for (int j = 1; j <= b; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + dp[i][j]; } } int ans = 0; for (int i = r; i <= a; i++) { for (int j = r; j <= b; j++) { ans = max(ans, dp[i][j] - dp[i - r][j] - dp[i][j - r] + dp[i - r][j - r]); } } cout << ans << '\n'; return 0; }