先说复杂度：$n^2 logn$ 可优化为 $n^2$

一、转化问题

看到这题的题面，突然想到了 P2466 [SDOI2008] Sue 的小球 这道题（核心内容没什么关系，不要被误导）

那么，相同点（废话）：

1. 都在数轴上
2. 数轴上都有一些点要使用
3. 对于每样东西都分为可用阶段和不可用阶段 且两阶段单调

相似点：

1. Sue这道题是小球会下落，落到某时刻就捡不到了，即先有用再没用
2. 而本题则是打卡点在t[i]时刻才会开启，即先没用再有用。

可以发现这是相反的，那么考虑将过程反过来做（以下就都已经反过来了）

现在问题变成了 一开始打卡点随便选，但在某时刻后打卡点会失效。设初始时间为time，最终时间是0

二、设置状态，考虑转移

现在，如果做过Sue这道题，可以直接套用dp状态

如果没做过，那我们来寻找一些性质：因为现在打卡点随便选，所以当我们经过一段区间时，区间内所有能用的点我们都会用，且最后定停在某一端上，自然可以区间dp，设f[i][j][0/1],表示已选完i到j个打卡点，目前停在i/j点的最小时间

转移：

f[i][j][0] <- f[i+1][j][0]+d[i][i+1] 或 f[i+1][j][1]+dxx

f[i][j][1] <- f[i][j-1][0]+dxx 或 f[i][j-1][1]+dxx

另外

1. 对于每一个区间，真正的答案是： 最大的 （区间内某点到达时间+t[此点] ），这个可以在转移时更新
2. 因为本题要求所有点都必须选，所以转移时要判断能否选，不能选就不转移了
3. 因为是倒着考虑，所以最开始在c点（赋初值），最后要去0点（最后答案）
4. 我们不知道什么时候结束，即time是多少，所以二分（好像不二分也行,可以把time设的很大，然后直接跑一遍出答案）

三、具体见代码：

f[][][].F记录在某一端点的到达时间，f[][][].S记录区间真答案

k1k2那一堆是转移的一大坨，太长所以换成k1k2了

#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
struct node{
	int x,t;
	bool operator<(const node y)const{
//		if(x==y.x) return t<y.t;
		return x<y.x;
	}
}d[1005];
int n,L,c,mx;
pair<int,int> f[1005][1005][5];
bool check(int tim){
//	cout<<tim<<' ';
	memset(f,0x3f,sizeof f);
	for(int i=1;i<=n;i++){
		if(abs(d[i].x-c)<=tim-d[i].t+1){
			f[i][i][0].F=f[i][i][1].F=abs(d[i].x-c);
			f[i][i][0].S=f[i][i][1].S=abs(d[i].x-c)+d[i].t;
		}
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			int k1=f[i+1][j][0].F+d[i+1].x-d[i].x;
			int k2=f[i+1][j][1].F+d[j].x-d[i].x;
			int k3=f[i][j-1][0].F+d[j].x-d[i].x;
			int k4=f[i][j-1][1].F+d[j].x-d[j-1].x;
			if(k1<=tim-d[i].t){
				if(f[i][j][0].F>=k1){
					f[i][j][0].F=k1;
					f[i][j][0].S=min(f[i][j][0].S,f[i+1][j][0].S);
				}
			}
			if(k2<=tim-d[i].t){
				if(f[i][j][0].F>=k2){
					f[i][j][0].F=k2;
					f[i][j][0].S=min(f[i][j][0].S,f[i+1][j][1].S);
				}
			}
			if(k3<=tim-d[j].t){
				if(f[i][j][1].F>=k3){
					f[i][j][1].F=k3;
					f[i][j][1].S=min(f[i][j][1].S,f[i][j-1][0].S);
				}
			}
			if(k4<=tim-d[j].t){
				if(f[i][j][1].F>=k4){
					f[i][j][1].F=k4;
					f[i][j][1].S=min(f[i][j][1].S,f[i][j-1][1].S);
				}
			}
			f[i][j][0].S=max(f[i][j][0].S,f[i][j][0].F+d[i].t);
			f[i][j][1].S=max(f[i][j][1].S,f[i][j][1].F+d[j].t);
//			cout<<i<<' '<<j<<' '<<f[i][j][0]<<' '<<f[i][j][1]<<'\n';
		}
	}
	int ans1=max(f[1][n][0].S,f[1][n][0].F+d[1].x);
	int ans2=max(f[1][n][1].S,f[1][n][1].F+d[n].x);
//	cout<<ans1<<' '<<ans2<<'\n';
	return tim>=min(ans1,ans2);
}
int main()
{
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	cin>>n>>L>>c;
	for(int i=1;i<=n;i++){
		cin>>d[i].x>>d[i].t;
		mx=max(mx,d[i].t);
	}
	sort(d+1,d+n+1);
	int l=mx,r=12000,mid,ans=-1;
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}

四、比答案少一怎么办

1、更新真答案的时候，59行写了吗

2、判断能否转移时，k<=tim-t[i] +1 ，不用+1