P3842 [TJOI2007] 线段

[TJOI2007] 线段

题目描述

在一个 $n\times n$ 的平面上，在每一行中有一条线段，第 $i$ 行的线段的左端点是$(i,L_i)$，右端点是$(i,R_i)$。

你从 $(1,1)$ 点出发，要求沿途走过所有的线段，最终到达 $(n,n)$ 点，且所走的路程长度要尽量短。

更具体一些说，你在任何时候只能选择向下走一步（行数增加 $1$）、向左走一步（列数减少 $1$）或是向右走一步（列数增加 $1$）。当然，由于你不能向上行走，因此在从任何一行向下走到另一行的时候，你必须保证已经走完本行的那条线段。

输入格式

第一行有一个整数 $n$。

以下 $n$ 行，在第 $i$ 行（总第 $(i+1)$ 行）的两个整数表示 $L_i$ 和 $R_i$。

输出格式

仅包含一个整数，你选择的最短路程的长度。

样例 #1

样例输入 #1

6
2 6
3 4
1 3
1 2
3 6
4 5

样例输出 #1

24

提示

我们选择的路线是

 (1, 1) (1, 6)
 (2, 6) (2, 3)
 (3, 3) (3, 1)
 (4, 1) (4, 2)
 (5, 2) (5, 6)
 (6, 6) (6, 4) (6, 6)

不难计算得到，路程的总长度是 $24$。

对于 $100\%$ 的数据中，$n\le 2\times 10^4$，$1\le L_i\le R_i\le n$。

正解

二维 dp。

一、状态：$dp[i][0/1]$ 表示从 $(1,1)$ 走到第 $i$ 条线段左端点或右端点的最短距离。

二、转移：分为四个部分。

1. 右端点转右端点：也就是从 $dp[i-1][1]$ 开始走，先走到现在的左端点，再走到现在的右端点，即 $dp[i-1][1]+abs(l[i]-r[i-1])+(r[i]-l[i]+1)$；
2. 左端点转右端点：也就是从 $dp[i-1][1]$ 开始走，先走到现在的左端点，再走到现在的右端点，即 $dp[i-1][0]+abs(l[i]-l[i-1])+(r[i]-l[i]+1)$，这时 $dp[i][1]=min(dp[i-1][1]+abs(l[i]-r[i-1])+(r[i]-l[i]+1),dp[i-1][0]+abs(l[i]-l[i-1])+(r[i]-l[i]+1))$；
3. 右端点转左端点：也就是从 $dp[i-1][0]$ 开始走，先走到现在的右端点，再走到现在的左端点，即 $dp[i-1][1]+abs(r[i]-r[i-1])+(r[i]-l[i]+1)$；
4. 左端点转左端点：也就是从 $dp[i-1][0]$ 开始走，先走到现在的右端点，再走到现在的左端点，即 $dp[i-1][0]+abs(r[i]-l[i-1])+(r[i]-l[i]+1)$，这时 $dp[i][0]=min(dp[i-1][1]+abs(r[i]-r[i-1])+(r[i]-l[i]+1),dp[i-1][0]+abs(r[i]-l[i-1])+(r[i]-l[i]+1))$。

三、答案：最后的结果可能停在左端点或右端点，都要走到 $(n,n)$，所以答案就是 $\min (dp[n][1]+n-r[n],dp[n][0]+n-l[n])$。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 20010;
int n,l[N],r[N],dp[N][2]; 

void solve()
{
	cin >> n;
	for (int i = 1;i <= n;i++)
		cin >> l[i] >> r[i];
	dp[1][0] = (r[1]-1) + (r[1]-l[1]);
	dp[1][1] = r[1]-1;
	for (int i = 2;i <= n;i++)
	{
		int rr = dp[i-1][1]+abs(l[i]-r[i-1])+(r[i]-l[i]+1);
		int lr = dp[i-1][0]+abs(l[i]-l[i-1])+(r[i]-l[i]+1);
		int rl = dp[i-1][1]+abs(r[i]-r[i-1])+(r[i]-l[i]+1);
		int ll = dp[i-1][0]+abs(r[i]-l[i-1])+(r[i]-l[i]+1);
		dp[i][1] = min(rr,lr);
		dp[i][0] = min(rl,ll);
	}
	cout << min(dp[n][1]+n-r[n],dp[n][0]+n-l[n]);
}

signed main()
{
	solve();
	printf("\n");
	return 0;
}