P3842 线段

题目大意

在 $n \times n$ 的格上，在每行中各有一条线段 $(i, l_i) \to (i, r_i)$。

你从 $(1,1)$ 出发，只能沿着格子直走，最终走到 $(n,n)$。要求沿途经过所有的线段，且所走路程长度尽量的短。

分析

显然是一行一行的递推。维护两个数据，一个是走完该行后停留在左侧的，记作 ${\rm DP}_l$，相应的停留在右侧的记作 ${\rm DP}_r$。

若停在左侧，可能从上一行的右侧走来，也可能是由左侧走来，故转移方程有

$${\rm DP}_l[i] = r_i - l_i + \min\{{\rm DP}_l[i - 1] + |l_{i-1} - r_i|, {\rm DP}_r[i - 1] + |r_{i - 1} - r_i|\}$$

右侧类似，故可以写出代码

int main() {
	int n = rr();
	ll past_l = 1, past_r = 1, dpl = 0, dpr = 0;
	for (ll i = 1; i <= n; i++) {
		ll l = rr(), r = rr();
		ll tl = min(dpl + abs(past_l - r), dpr + abs(past_r - r)) + r - l;
		ll tr = min(dpl + abs(past_l - l), dpr + abs(past_r - l)) + r - l;
		dpl = tl, dpr = tr;
		past_l = l, past_r = r;
	}
	printf("%lld\n", min(dpl + n - past_l, dpr + n - past_r) + n - 1);
	return 0;
}