自动搬运

查看原文

来自洛谷，原作者为

	zhoukangyang ^w^/

搬运于2025-08-24 22:16:28，当前版本为作者最后更新于2020-08-29 13:21:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻语

有神仙让蒟蒻讲思路, 蒟蒻就写了篇题解 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$ 的节点。

$f_i$ 是 $min(f_{1,2...i-1})$ , 显然每次把 $f$ 值丢进树状数组里面就可以单次 $O(\log n)$ 维护了

如果 $i$ 是一个跳板的末端, 直接更新一下就好了qwq

最后答案就是 $min(f_i + n + n)$ (如果把他当作一个节点, 那么 $f$ 值就是 $min(f_i)$, 所以答案是 $min(f_i + n + n)$)

细节看蒟蒻丑陋的代码吧 qwq

#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;
}