UVa 10360 Rat Attack:枚举和优化

UVa 10360 Rat Attack:枚举和优化2014-07-07 synapse7 http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1301

由于格子数远大于鼠窝，所以以鼠窝为出发点，增加鼠窝周围d范围内的“格子的值”，最后扫描每个格子输出最大格子值即可。

完整代码：

01./*0.125s*/02.03.#include<bits/stdc++.h>04.using namespace std;05.const int MAXN = 1030;06.07.int cnt[MAXN][MAXN];08.09.int main（）10.{11.int T, d, n, i, j, p, q;12.int x, y, num, lmax;13.int x_min, x_max, y_min, y_max;14.scanf（"%d", &T）;15.while （T--）16.{17.scanf（"%d%d", &d, &n）;18.memset（cnt, 0, sizeof（cnt））;19.for （i = 0; i < n; ++i）20.{21.scanf（"%d%d%d", &x, &y, &num）;22.x_min = max（0, x - d）, x_max = min（1024, x + d）;23.y_min = max（0, y - d）, y_max = min（1024, y + d）;24.for （p = x_min; p <= x_max; ++p）25.for （q = y_min; q <= y_max; ++q）26.cnt[p][q] += num;27.}28.lmax = x = y = 0;29.for （i = 0; i < 1025; ++i）30.for （j = 0; j < 1025; ++j）31.if （cnt[i][j] > lmax）32.x = i, y = j, lmax = cnt[i][j];33.printf（"%d %d %d
", x, y, lmax）;34.}35.return 0;36.}