luogu P3842 [TJOI2007]线段

题目大意

平面上有 $n$ 条线段，这些线段都与x轴平行且端点都在格点上，且都在(1,1)与(n,n)之间。计算从(1,1)出发到(n,n)结束并覆盖每一条线段的所有路径中，路程最短的路程。

解题思路

不难想到动态规划。对于每条线段，只有两种状态：左侧进入右侧离开，右侧进入左侧离开。不难写出转移方程。

#include 
#include 
#include 


#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?(x):(-(x)))
const int MAXN=20010;

int n;
int l[MAXN], r[MAXN];
//f[i][j]表示走到第i行线段的左边0或右边1的最优解 
int f[MAXN][5];


int main (){
	scanf ("%d", &n);
	for (int i=1; i<=n; ++i)
		scanf ("%d%d", &l[i], &r[i]);
	f[1][0]=l[1]-1+(r[1]-l[1])*2; f[1][1]=r[1]-1;
	for (int i=2; i<=n; ++i){
		f[i][1]=min (f[i-1][0]+abs (l[i-1]-l[i])+1, f[i-1][1]+abs (r[i-1]-l[i])+1)+r[i]-l[i];
		f[i][0]=min (f[i-1][0]+abs (l[i-1]-r[i])+1, f[i-1][1]+abs (r[i-1]-r[i])+1)+r[i]-l[i];
	}
	printf ("%d", min (f[n][0]+n-l[n], f[n][1]+n-r[n]));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26