题解：P10988 [蓝桥杯 2023 国 Python A] 走方格
I_Love_DS
·
·
题解
前言
水一发理论复杂度比 bfs 低但常数超大，比 bfs 还慢的解法。（可能是假的，因为算法标签没有标）
思路
首先，我们发现小人只能往下走，不能往上走。这让我联想到了P7074 方格取数。和本题也有异曲同工之妙，因为那道题只能往右走，不能往左走。
因为“反复横跳”是没有意义的（也就是不优的），所以我们可以不考虑往右走完又往回走的情况。
所以，考虑从上往下 DP。设 f_{i,j} 表示走到 i 行 j 列最小代价。有如下转移式：
- 当 $k<j$ 时，$a_{i, k} < a_{i, k + 1} < \dots < a_{i, j}$；
- 当 $k>j$ 时，$a_{i, k} < a_{i, k - 1} < \dots < a_{i, j}$。
转移式的第一部分是从左边来，第二部分是从上面来，第三部分统称是快速移动。
但这还是 $O(n^3)$ 的怎么办？
你看，这个转移式的瓶颈在枚举 $k$ 上。然鹅其实不必那么麻烦，直接拿一个数据结构：线段树！
她支持动态单点修改和区间求最小值，她再合适不过了！
~~线段树 /qq~~
所以时间复杂度降到了 $O(n^2 \log n)$。~~虽然这不是最优解但是这是复杂度最优的做法~~
## 代码
欢迎 Hack 或指出错误或证伪。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 50;
int n;
int a[N][N], f[N][N];
int l[N], r[N];
int t[4 * N];
void buildtree(int k, int l, int r) {
if (l == r) {
t[k] = 1 << 30;
return;
}
int m = (l + r) / 2;
buildtree(k + k, l, m);
buildtree(k + k + 1, m + 1, r);
t[k] = min(t[k + k], t[k + k + 1]);
}
void update(int k, int l, int r, int x, int y, int z) {
if (l == x && r == y) {
t[k] = min(t[k], z);
return;
}
int m = (l + r) / 2;
if (y <= m) update(k + k, l, m, x, y, z);
else if (x > m) update(k + k + 1, m + 1, r, x, y, z);
else update(k + k, l, m, x, m, z), update(k + k + 1, m + 1, r, m + 1, y, z);
t[k] = min(t[k + k], t[k + k + 1]);
}
int calc(int k, int l, int r, int x, int y) {
if (l == x && r == y) return t[k];
int m = (l + r) / 2;
if (y <= m) return calc(k + k, l, m, x, y);
else if (x > m) return calc(k + k + 1, m + 1, r, x, y);
else return min(calc(k + k, l, m, x, m), calc(k + k + 1, m + 1, r, m + 1, y));
}
// 以上是线段树模板
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
int x;
x = 1;
f[1][1] = 0;
for (int i = 2; i <= n; i++) {
if (a[1][i] >= a[1][i - 1]) x = i;
f[1][i] = f[1][i - 1] + 1;
if (x != i) f[1][i] = min(f[1][i], f[1][x] + 1);
}
for (int i = 2; i <= n; i++) {
buildtree(1, 1, n);
//memset(l, 0, sizeof(l));
l[1] = f[i - 1][1] + 1; update(1, 1, n, 1, 1, l[1]);
x = 1;
for (int j = 2; j <= n; j++) {
if (a[i][j] >= a[i][j - 1]) x = j;
l[j] = min(f[i - 1][j] + 1, l[j - 1] + 1);
if (x != j) l[j] = min(l[j], calc(1, 1, n, x, j - 1) + 1);
update(1, 1, n, j, j, l[j]);
} // 从左面来
buildtree(1, 1, n);
//memset(r, 0, sizeof(r));
r[n] = f[i - 1][n] + 1; update(1, 1, n, n, n, r[n]);
x = n;
for (int j = n - 1; j; j--) {
if (a[i][j] >= a[i][j + 1]) x = j;
r[j] = f[i - 1][j] + 1;
if (x != j) r[j] = min(r[j], calc(1, 1, n, j + 1, x) + 1);
update(1, 1, n, j, j, r[j]);
} // 从右面来
f[i][1] = min({l[1], r[1], f[i - 1][1] + 1});
for (int j = 2; j <= n; j++) f[i][j] = min({f[i - 1][j] + 1, f[i][j - 1] + 1, l[j], r[j]}); // 更新 dp 数组
}
printf("%d\n", f[n][n]);
return 0;
}
```
~~没卡常你们卡去吧~~