这题要考虑锤子移动到网格外部的情况,否则WA,处理的方式就是行和列同时增加5(最大距离).
详见代码:
#include <cstdlib> #include <cstring> #include <cstdio> #include <algorithm> #include <iostream> using namespace std; /* 题意:给定一个N*N的矩阵, 然后在这个矩阵的每个格子在任意时间会出现一个鼹鼠,这个出现 出现鼹鼠的时间是输出信息所确定的. 现在你手里有一把锤子能够去锤这些鼹鼠. 你能 够移动锤子,移动的两点之间的距离不能超过d,且中心在这条路径上的鼹鼠到都要受到 打击. 每个鼹鼠出现的时间值维持一秒钟. 现在问在一次游戏中最多打到多少鼹鼠 解法:dp[k][i][j]第k分钟在[i, j]点时的最多打到的鼹鼠个数. 那么有动态方程: dp[k][i][j] = max(dp[k-1][m][n] + online); 其中sum为在(m,n)->(i,j)这条长度最多d 的线上的且在第k-1分钟出现的鼹鼠的个数. */ int N, d, M, MaxTi, dp[15][35][35]; char G[12][35][35]; bool judge(int &x1, int &y1, int &x2, int &y2) { return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) <= d*d; } int online(int k, int x1, int y1, int x2, int y2) { int ret = 0; if (x1 > x2) { swap(x1, x2); swap(y1, y2); }// 将两个点的关系做一个转换 if (x1 == x2) { if (y1 > y2) swap(y1, y2); for (int j = y1; j <= y2; ++j) { if (G[k-1][x1][j]) ++ret; } return ret; } if (y1 == y2) { for (int i = x1; i <= x2; ++i) { if (G[k-1][i][y1]) ++ret; } return ret; } for (int i = x1; i <= x2; ++i) { if ((y2*(i-x1)-y1*(i-x2))%(x2-x1) == 0) { if (G[k-1][i][(y2*(i-x1)-y1*(i-x2))/(x2-x1)]) { ++ret; } } } return ret; } int DP() { ++MaxTi; // MaxTi出现的鼹鼠要等到MaxTi+1的时候才能够清理完 int L, R, U, D, ret = 0; // 四个坐标对d以内的可能点的范围给出一个约束 N += 10; // 由于可以移动到网格的外面,所以要加上10 for (int k = 2; k <= MaxTi; ++k) { // 直接计算到最后出现鼹鼠的 for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { dp[k][i][j] = 0; // 初始化 // 距离在d以内的点肯定出现在下面的正方形区域内,一个剪枝 U = max(i-d, 0), D = min(i+d, N-1); L = max(j-d, 0), R = min(j+d, N-1); for (int m = U; m <= D; ++m) { for (int n = L; n <= R; ++n) { if (judge(i, j, m, n)) { dp[k][i][j] = max(dp[k][i][j], dp[k-1][m][n]+online(k, i, j, m, n)); ret = max(ret, dp[k][i][j]); } } } } } } return ret; } int main() { int x, y, ti; while (scanf("%d %d %d", &N, &d, &M), N|d|M) { // 判断距离的时候直接用平方进行比较,避免浮点精度出错 MaxTi = -1; memset(G, 0, sizeof (G)); for (int i = 0; i < M; ++i) { scanf("%d %d %d", &x, &y, &ti); MaxTi = max(MaxTi, ti); G[ti][x+5][y+5] = 1; // 让坐标偏移5个单位 } printf("%d\n", DP()); } return 0; }