激光炸弹

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

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5010;
int N, R;
int g[maxn][maxn];
int ans;
int main() {
    ios::sync_with_stdio(0);
    cin >> N >> R;
    int xx = R, yy = R;
    for (int i = 0,x,y,w; i < N; ++i) {
        cin >> x >> y >> w;
        x++; y++;
        g[x][y] = w;
        xx = max(xx, x);
        yy = max(yy, y);
    }
    for (int i = 1; i <= xx; i++)
        for (int j = 1; j <= yy; j++)
            g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + g[i][j];
  
    for (int i = R; i <= xx; i++) {
        for (int j = R; j <= yy; j++) {
            ans = max(ans, g[i][j] - g[i - R][j] - g[i][j - R] + g[i - R][j - R]);
        }
    }
    cout << ans << endl;
    return 0;
}

 

上一篇:java蓝桥杯2016决赛路径之谜


下一篇:hdu1078 dfs+dp(记忆化搜索)搜索一条递增路径,路径和最大,起点是(0,0)