你说得对，但是网上所有做法在我这儿都 AC 不了。对了悬关。
by Breath_of_the_Wild @ 2024-03-30 19:53:39
@[Breath_of_the_Wild](/user/964817) 两边平方就不需要开根和 `double` 了。
by Nagasaki_Soyo @ 2024-03-30 19:58:50
@[Nagasaki_Soyo](/user/1081109) 但是还超时。能帮我优化优化吗。
$1\le n,m\le 1000,1\le d\le 100$，$d$ 最多一位小数
by Breath_of_the_Wild @ 2024-03-30 20:05:51
@[Breath_of_the_Wild](/user/964817)
```cpp
inline int dist(int a, int b, int c, int d) {
return (a - c) * (a - c) + (b - d) * (b - d);
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> d;
clock_t st = clock();
int dd = d * d * 100;
memset(ans, 0x7f, sizeof ans);
ans[1][1] = 0;
for (int i = 1; i <= n; i++) {
for (int k = i; k <= i + d && k <= n; k++)
now[k] = 1; // 第 k 行至多走到 now[k] 的位置
for (int j = 1; j <= m; j++) {
for (int k = i; k <= i + d && k <= n; k++) {
while (now[k] <= m && dist(i, j, k, now[k]) * 100 <= dd)
chkmin(ans[k][now[k]], ans[i][j] + 1), now[k]++;
}
}
}
cout << ans[n][m] << '\n';
fprintf(stderr, "%.4lf ms\n", 1e3 * (clock() - st) / CLOCKS_PER_SEC);
return 0;
}
```
by Nagasaki_Soyo @ 2024-03-30 21:35:37
双指针做到 $O(n^2d)$。
by Nagasaki_Soyo @ 2024-03-30 21:50:37