题解：CF677D Vanya and Treasure

· · 题解

solution

题解基本全是根号做法，这里来个不一样的。

考虑朴素的 dp，遍历所有数字，对于每一个数字，设 dp_{i,j} 表示在 \{i,j\} 这个位置最少走多少步，显然当前数字的所有位置可以由上一个数字的所有位置转移过来，转移时简单的。

但这样无法通过，考虑优化，设从 \{x_1,y_1\} 转移到 \{x_2,y_2\}，不妨设 x_1<x_2 且 y_1<y_2，则其间的距离为 | x_2-x_1 |+| y_2-y_1| 拆开即为 x_2+y_2-x_1-y_2，所以每次转移相当于找到前面一个数时最小的 dp_{x_1,y_1}-x_1-y_1 再加上 x_2+y_2，把每个颜色的对应位置存下来，用二维树状数组维护即可。

这里只是从左上转移到右下的情况，需要旋转三次得到其他方向的答案。