考虑区间DP，你发现走的时候，按照顺序从左往右依次走肯定不优，因为打卡地点有开门时间，所以正确做法是在打卡地之间反复地跑。

先按照横坐标排序，然后你设 $dp_{i,j,0}$ 一开始 [i,j] 全部没打卡，且除此之外全打了卡，然后现在又到了 $i$，最小时间是多少。 类似地，$dp_{i,j,1}$ 表示在 $j$ 的最小时间。

然后转移的时候 $dp_{i,j,0}$ 可以从 $dp_{i-1,j,0}$ 和 $dp_{i,j+1,1}$ 转移过来，$dp_{i,j,1}$ 可以从 $dp_{i-1,j,0}$ 和 $dp_{i,j+1,1}$ 转移过来。也就是从外边第一个往里边转移。

为什么这样是对的呢，因为如果除了 [i,j] 没转移，那么他可以从 $1,2$...$i-1$ 和 $j+1,j+2$...$n$ 走过来，然后其实就相当于从 $i-1$，$j+1$ 走过来，因为如果从别的地方过来，一定会经过他们。

你枚举 $i$ 和 $j$ 的时候 $i$ 从小往大，$j$ 从大往小，可以保证从大区间推到小区间，最后的答案就是

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,l,c;
struct node {
	int x,t;
} a[1005];
int dp[1005][1005][2];
bool ccf(node A,node B) {
	return A.x<B.x;
}
void check(int mid) {
	memset(dp,0x3f,sizeof dp);
	dp[1][n][0]=max(a[1].t,a[1].x),dp[1][n][1]=max(a[n].t,a[n].x);
	for(int i=1; i<=n; ++i) {
		for(int j=n; j>=i; --j) {
			dp[i][j][0]=min(dp[i][j][0],min(
			                    max(dp[i-1][j][0]+a[i].x-a[i-1].x,a[i].t),
			                    max(dp[i][j+1][1]+a[j+1].x-a[i].x,a[i].t
			                       )));
			dp[i][j][1]=min(dp[i][j][1],min(
			                    max(dp[i-1][j][0]+a[j].x-a[i-1].x,a[j].t),
			                    max(dp[i][j+1][1]+a[j+1].x-a[j].x,a[j].t
			                       )));
		}
	}
}
signed main() {
	cin>>n>>l>>c;
	for(int i=1; i<=n; ++i) {
		cin>>a[i].x>>a[i].t;
	}
	sort(a+1,a+1+n,ccf);
	check(0);
	int ans=0xccfccfccfccf;
	for(int i=1; i<=n; ++i) {
		ans=min(ans,max(abs(c-a[i].x)+dp[i][i][0],0ll));
	}
	cout<<ans<<"\n";
	return 0;
}

对了顺便提一句，如果写了函数一定要看有没有 return 或有没有 void，因为如果其他类型的函数没有返回值的话，他就会跳转到一个未知的地方导致堆栈错误，Windows系统没事，但是Linux系统下就爆炸。

然后我一开始想二分，于是把DP写到bool类型的check函数里，后来发现不用二分然后忘了改类型，于是喜提0分的好成绩。

吃一堑，饱一顿 ——Dzl

在编译器选项里面加入命令-Wall可以有效避免此类型的UB

先说复杂度：$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