/doge薛昊老是偷我题做，最近我也就拿他博客上的题来练练手。其中这道题真的什么思路都没有，这个区间DP的套路我还真没碰到过。
这是一个大区间推小区间的套路。
题意：
小明要在某层楼的各个老师那里交一大堆作业，但是小明来早了，老师还没上班，他站在这层楼的最左边，告诉你每个老师的上班时间，最后要在某个给定位置下楼，问最少时间。
思路：
shit，完全是看博客，看代码敲的。
一个比较困难的点在于给定离开地点，算了，不装了，就算取消这个条件我也写不来……
明确可以用dp求解，首先按照位置优先开门顺序次优的顺序排序，设三维数组 $dp[l][r][k]$。
当 $k=0$ 时，表示只有 $(l,r] $ 区间内的作业没有交。
而 $k=1$ 时，表示只有 $[l,r) $ 区间内的作业没有交。
而我们的其实状态$dp[1][n][0/1]$是已知的，我们完全可以由此不断向内挤压求出小区间的结果。
当 $l=r$ 时，则所有作业交完，且停在 $l$ 点。
AC Code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))
using namespace std;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
int dp[maxn][maxn][2];
pii point[maxn];
int getDis(int d, int s) { return point[d].first - point[s].first; }
int main()
{
int n, h, b;
scanf("%d %d %d", &n, &h, &b);
range(i, 1, n) scanf("%d %d", &point[i].first, &point[i].second);
sort(point + 1, point + 1 + n);
fill(dp, 0x3f);
dp[1][n][0] = max(point[1].first, point[1].second);
dp[1][n][1] = max(point[n].first, point[n].second);
rrange(len, 1, n - 1) range(l, 1, n + 1 - len)
{
int r = l + len - 1;
if (l > 1) {
dp[l][r][0] = min(dp[l][r][0], dp[l - 1][r][0] + getDis(l, l - 1));
dp[l][r][1] = min(dp[l][r][1], dp[l - 1][r][0] + getDis(r, l - 1));
}
if (r < n) {
dp[l][r][0] = min(dp[l][r][0], dp[l][r + 1][1] + getDis(r + 1, l));
dp[l][r][1] = min(dp[l][r][1], dp[l][r + 1][1] + getDis(r + 1, r));
}
dp[l][r][0] = max(dp[l][r][0], point[l].second);
dp[l][r][1] = max(dp[l][r][1], point[r].second);
}
int ans = inf;
range(i,1,n) ans = min(ans,dp[i][i][0]+abs(b-point[i].first));
printf("%d\n",ans);
return 0;
}