https://www.acwing.com/problem/content/515/
二维前缀和暴力统计，注意最后放这些点的位置的时候可以放在角落里的，巨坑，应该最简单的思路是枚举每个点1~MAXN，然后写个函数自动返回他周围的点的和。
#include <bits/stdc++.h> using namespace std; const int MAXN = 129; int sum[MAXN + 25][MAXN + 25]; int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); #endif // Yinku int d, n; scanf("%d%d", &d, &n); d *= 2; while(n--) { int x, y, k; scanf("%d%d%d", &x, &y, &k); ++x, ++y; sum[x][y] += k; } for(int i = 1; i <= MAXN + d / 2; ++i) { for(int j = 1; j <= MAXN + d / 2; ++j) { sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; //printf("%2d", sum[i][j]); } //printf("\n"); } int ans2 = 0; for(int i = d + 1; i <= MAXN + d / 2; ++i) { for(int j = d + 1 ; j <= MAXN + d / 2; ++j) { ans2 = max(ans2, sum[i][j] - sum[i - (d + 1)][j] - sum[i][j - (d + 1)] + sum[i - (d + 1)][j - (d + 1)]); //printf("%2d", sum[i][j] - sum[i - (d + 1)][j] - sum[i][j - (d + 1)] + sum[i - (d + 1)][j - (d + 1)]); } //printf("\n"); } int ans1 = 0; for(int i = d / 2 + 1; i <= MAXN + d / 2; ++i) { for(int j = d / 2 + 1 ; j <= MAXN + d / 2; ++j) { if(sum[i][j] - ((i >= d + 1) ? sum[i - (d + 1)][j] : 0) - ((j >= d + 1) ? sum[i][j - (d + 1)] : 0) + ((i >= d + 1 && j >= d + 1) ? sum[i - (d + 1)][j - (d + 1)] : 0) == ans2) ++ans1; } } printf("%d %d\n", ans1, ans2); return 0; }AcWing - 513 - 无线网络发射器选址 = 前缀和
标签：
原文地址：https://www.cnblogs.com/Inko/p/11664034.html