Description

# [USACO04OPEN] Turing in Homework G ## 题目描述 贝茜有 $ C $ ( $ 1 \leq C \leq 1000 $ )门科目的作业要上交，之后她要去坐艿(nuai)哝(nong)同学和巴士(EasonLiang)回家。 每门科目的老师所在的教室排列在一条长为 $ H $ ( $ 1 \leq H \leq 1000 $ )的走廊上，他们只在课后接收作业，交作业不需要时间。贝茜现在在位置0，她会告诉你每个教室所在的位置，以及走廊出口的位置。她每走1个单位的路程，就要用1秒。她希望你计算最快多久以后她能交完作业并到达出口。 ## 输入格式 第一行：三个整数 $C$，$H$ 和 $B$，$1 \le C \le 1000,1 \le H \le 1000,0 \le B \le H$。 第二行到 $C+1$ 行：第 $i+1$ 行有两个整数 $X_i$ 和 $T_i$，$0 \le X_i \le H,0 \le T_i \le 10000$。 $B$ 表示车站位置。 $X_i$ 表示第 $i$ 份作业应该在 $X_i$ 这个位置交。 $T_i$ 表示这个位置（教室）的这个科目老师（也就是收这份作业的老师）下课的时间。 ## 输出格式 单个整数，表示贝西交完作业后走到车站的最短时间 ## 样例 #1 ### 样例输入 #1 ``` 4 10 3 8 9 4 21 3 16 8 12 ``` ### 样例输出 #1 ``` 22 ``` ## 提示 走到坐标 8 处，第 9 分钟交一本作业，等到第 12 分钟时，交另一本作业。再走到坐标 4 处交作业，最后走到坐标 3 处，交最后一本作业，此地就是车站所在位置，共用时 22 分钟

Hint

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e3+10;
LL f[N][N][2];
struct node{LL x, t;} a[N];
bool cmp(node n1, node n2){
	return n1.x<n2.x;
}
int main(){
	int n, H, ex; scanf("%d%d%d", &n, &H, &ex);
	for(int i=1; i<=n; i++){
		scanf("%lld%lld", &a[i].x, &a[i].t);
	}
	sort(a+1, a+n+1, cmp);
	memset(f, 0x3f, sizeof(f));
	f[1][n][0]=max(a[1].x, a[1].t);
	f[1][n][1]=max(a[n].x, a[n].t);
	for(int i=1; i<=n; i++){
		for(int j=n; j>=i; j--){
			f[i][j][0]=min({f[i][j][0], max(f[i-1][j][0]+a[i].x-a[i-1].x
			, a[i].t), max(f[i][j+1][1]+a[j+1].x-a[i].x, a[i].t)});
			
			f[i][j][1]=min({f[i][j][1], max(f[i-1][j][0]+a[j].x-a[i-1].x
			, a[j].t), max(f[i][j+1][1]+a[j+1].x-a[j].x, a[j].t)});
		}
	}
	LL ans=1e14;
	for(int i=1; i<=n; i++){
		ans=min(ans, min(f[i][i][0], f[i][i][1])+abs(a[i].x-ex));
	}
	printf("%lld\n", ans);
	return 0;
}