题解 P6007 【[USACO20JAN]Springboards G】
zhoukangyang
·
·
题解
蒟蒻语
有神仙让蒟蒻讲思路, 蒟蒻就写了篇题解 qwq
蒟蒻解
先将所有坐标的 y 坐标离散化。
然后把所有坐标按照 x 为第一关键字, y 为第二关键字排序。
从前往后遍历, 用 dp_i 表示从 (0, 0) 到 x_i, y_i 的答案。
怎么更新信息?
考虑用 k 节点更新 i 节点。
如果 k 节点可以直接用跳板直接跳到 i 节点, 那么 dp 值相同。
否则要一步一步走过去。如果能更新, 那么 dp_i = dp_k + x_i - x_k + y_i - y_k
那么 dp_i - x_i - y_i = dp_k - x_k - y_k
如果设 f_i = dp_i - x_i - y_i，那么 f_i = f_k !
那么现在丢掉 dp 数组然后使用 f 数组。
现在如果k 节点可以直接用跳板直接跳到 i 节点
f_i = dp_i - x_i - x_j = dp_k - x_i - y_i = f_k + x_k + y_k - x_i - y_i
那么考虑谁能够更新他呢？
只有 x 坐标小于等于他而且 y 坐标小于等于他的节点可以更新。
这时显然 x 坐标小于等于 i 节点已经满足, 而 y 坐标没有满足。 现在要求 y 坐标处于 0 ... y_i 的节点。
如果 $i$ 是一个跳板的末端, 直接更新一下就好了qwq
最后答案就是 $min(f_i + n + n)$ (如果把他当作一个节点, 那么 $f$ 值就是 $min(f_i)$, 所以答案是 $min(f_i + n + n)$)
细节看蒟蒻丑陋的代码吧 qwq
```cpp
#include<bits/stdc++.h>
#define N 200010
using namespace std;
int n, m, a[N], fr[N], to[N], Ans;
struct node {
int x, y, yy, id;
} p[N];
bool cmp(node aa, node bb) {
return aa.x == bb.x ? aa.y < bb.y : aa.x < bb.x;
}
bool ycmp(node aa, node bb) {
return aa.y < bb.y;
}
int ans[N];
void add(int x, int val) {
for(; x <= m * 2; x += (x & -x)) ans[x] = min(ans[x], val);
}
int qzh(int x) {
int Ans = 0;
for(; x; x -= (x & -x)) Ans = min(Ans, ans[x]);
return Ans;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d%d", &p[i].x, &p[i].y), p[i].id = i;
scanf("%d%d", &p[i + m].x, &p[i + m].y), p[i + m].id = i;
}
sort(p + 1, p + m * 2 + 1, ycmp);
p[0].y = -1;
for(int i = 1; i <= 2 * m; i++) p[i].yy = p[i - 1].yy + (p[i - 1].y != p[i].y);
sort(p + 1, p + m * 2 + 1, cmp);
for(int i = 1; i <= m * 2; i++) {
if(fr[p[i].id]) to[p[i].id] = i;
else fr[p[i].id] = i;
}
for(int i = 1; i <= m * 2; i++) {
a[i] = min(a[i], qzh(p[i].yy));
if(fr[p[i].id] == i) a[to[p[i].id]] = min(a[to[p[i].id]],
a[i] + p[i].x + p[i].y - p[to[p[i].id]].x - p[to[p[i].id]].y);
add(p[i].yy, a[i]);
Ans = min(Ans, a[i]);
}
printf("%d\n", Ans + n * 2);
return 0;
}
```