二位前缀和DP大水题
——代码
1 #include <cstdio> 2 #include <iostream> 3 4 const int MAXN = 5010; 5 int n, r, ans; 6 int sum[MAXN][MAXN]; 7 8 inline int read() 9 { 10 int x = 0, f = 1; 11 char ch = getchar(); 12 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 13 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 14 return x * f; 15 } 16 17 inline int max(int x, int y) 18 { 19 return x > y ? x : y; 20 } 21 22 int main() 23 { 24 int i, j, x, y, z; 25 n = read(); 26 r = read(); 27 for(i = 1; i <= n; i++) 28 { 29 x = read(); 30 y = read(); 31 sum[x + 1][y + 1] = read(); 32 } 33 for(i = 1; i <= 5001; i++) 34 for(j = 1; j <= 5001; j++) 35 sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; 36 for(i = r; i <= 5001; i++) 37 for(j = r; j <= 5001; j++) 38 ans = max(ans, sum[i][j] - sum[i - r][j] - sum[i][j - r] + sum[i - r][j - r]); 39 printf("%d ", ans); 40 return 0; 41 }