更好的阅读体验： https://blog.csdn.net/tenkuo/article/details/163498113

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 5010;
 
struct node {
	LL x, t;
} a[N * 2];
 
LL dp[2 * N][2], p[2 * N][2];
// 两倍 N 就会炸空间，使用滚动数组 
// dp[l][r][0]：守卫在 l，只剩 [l, r] 没有被熄灭 的最小时间
// dp[l][r][1]：守卫在 r，只剩 [l, r] 没有被熄灭 的最小时间
 
// 为什么是闭区间？因为守卫可以选择不熄灭那个位置上的灯，这样方便计算
// 隐含规则：必须在合法的时间才能走到 l 或者 r（后面代码会讲）
 
bool cmp(node na, node nb) {
	if (na.x != nb.x) {
		return na.x < nb.x;
		// 保证 dp 处理从左到右 
	}
	return na.t < nb.t;
	// 按时间顺序排（一般情况不影响答案） 
}
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		LL l, r, t;
		cin >> l >> r >> t;
		a[i * 2 - 1] = {l, t};
		a[i * 2] = {r, t};
	}
	
	n *= 2;
	sort (a + 1, a + n + 1, cmp);
	memset(dp, 0x7f, sizeof(dp));
	LL inf = dp[0][0];
	memset(p, 0, sizeof(p));
	// p 数组代表的是上一个 len 的 dp 数组
	// 第一次转移时范围是 [1, n]，不存在什么 len = n + 1
	// 所以不会用到，不初始化也行 
	
	dp[1][0] = max(a[1].x, a[1].t);
	// dp[1][n][0] 
	dp[1][1] = max(a[n].x, a[n].t);
	// dp[1][n][1]
	
	LL ans = inf;
	for (int len = n; len >= 1; len --) {
		for (int i = 1; i + len - 1 <= n; i ++) {
			int j = i + len - 1;
			// 下面二维数组，想象中间维数插了个 [j] 
			if (i >= 2) {
				// 守卫从 i - 1 走到 i
				dp[i][0] = min(dp[i][0], p[i - 1][0] + a[i].x - a[i - 1].x);
				// 守卫从 i - 1 走到 j  
				dp[i][1] = min(dp[i][1], p[i - 1][0] + a[j].x - a[i - 1].x);
			}
			if (j <= n - 1) {
				// 守卫从 j + 1 走到 i 
				dp[i][0] = min(dp[i][0], p[i][1] + a[j + 1].x - a[i].x);
				// 守卫从 j + 1 走到 j 
				dp[i][1] = min(dp[i][1], p[i][1] + a[j + 1].x - a[j].x);
			}
			dp[i][0] = max(dp[i][0], a[i].t);
			dp[i][1] = max(dp[i][1], a[j].t);
			// 这里就是隐含规则，当前状态 i 或 j 是没有熄灭的
			// 但你必须在 a[i].t 或 a[j].t 及之后时刻到这里
			
			if (len == 1) {
				// 当 len = 1 时，代表 i = j，只有 [i, i] 没被熄灭
				// 手动操作一下就熄灭了，直接统计答案  
				ans = min(ans, min(dp[i][0], dp[i][1]));
			}
		}
		for (int i = 1; i <= n; i ++) {
			p[i][0] = dp[i][0];
			p[i][1] = dp[i][1];
			dp[i][0] = inf;
			dp[i][1] = inf;
			// 更新 p 数组，并初始化 dp数组 
		} 
	} 
	
	cout << ans << "\n";
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
struct N{
	ll x,t;
}a[10010];
bool cmp(N a,N b){
	if(a.x!=b.x)return a.x<b.x;
	return a.t<b.t;
}
ll dp[2][10010][2];//dp[i][j][0/1]表示只剩下i~j之间的点没有走，现在在i/j的最小时间 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		ll l,r,t;
		cin>>l>>r>>t;
		a[i*2-1]={l,t};
		a[i*2]={r,t};
		//将区间拆成两个点，显然在要先走到其中一个点，之后在走到另一个点的过程中区间会被填满 
	}
	n<<=1;
	memset(dp,0x3f,sizeof(dp));
	sort(a+1,a+1+n,cmp);
	int now=0;
	dp[now][n][0]=max(a[1].x,a[1].t);
	dp[now][n][1]=max(a[n].x,a[n].t);
	for(int i=n-1;i;i--){//先转移i=1的情况 
		dp[now][i][0]=max(a[1].t,dp[now][i+1][1]+abs(a[1].x-a[i+1].x));
		dp[now][i][1]=max(a[i].t,dp[now][i+1][1]+abs(a[i].x-a[i+1].x));
	}
	ll ans=2e18;
	now^=1;
	for(int i=2;i<=n;i++,now^=1){//由于是滚动数组，要枚举的是i，从[i-1,j]和[i,j+1]转移过来只需要记录上一个i和倒序枚举j即可 
		memset(dp[now],0x3f,sizeof(dp[now]));
		for(int j=n;j>=i;j--){
			dp[now][j][0]=min(dp[now][j][0],dp[now^1][j][0]+abs(a[i-1].x-a[i].x));//简单的转移 
			dp[now][j][1]=min(dp[now][j][1],dp[now^1][j][0]+abs(a[i-1].x-a[j].x));
			if(j<n){
				dp[now][j][0]=min(dp[now][j][0],dp[now][j+1][1]+abs(a[j+1].x-a[i].x));
				dp[now][j][1]=min(dp[now][j][1],dp[now][j+1][1]+abs(a[j+1].x-a[j].x));
			}
			dp[now][j][0]=max(dp[now][j][0],a[i].t);
			dp[now][j][1]=max(dp[now][j][1],a[j].t);
			if(i==j){//i=j就是全部被满足 
				ans=min(ans,min(dp[now][j][0],dp[now][j][1]));
			}
		}
	}
	cout<<ans;
	return 0;
}

题目大意:

需要我们在特定的时间后熄灭 $l$ 到 $r$ 盏灯，初始时在原点上。

思路:

有一个特别难想的做法，可以将区间拆解为两个点在 $t$ 这个时刻之前这两盏灯不能熄灭，所以可以先对它进行排序。然后设计区间 $DP$。$dp_{i,j,0/1}$ 表示除了 $i$ 和 $j$ 之间的灯是亮的其他都熄灭了且当前在区间的最左边或最右边。每一种情况都可以由 $i-1$ 和 $j+1$ 转移过来（详细转移请看代码），但是要和时间取一个最大值，因为没到时间不能熄灭。最后因为空间会爆，所以要记录上一个长度的 $dp$ 数组，来消掉一维。

三维代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5005;
const ll inf=LONG_LONG_MAX;
ll dp[2*N][2*N][2];
struct node{
	ll x,t;
}a[2*N];
bool cmp(node x,node y){
	if(x.x==y.x){
		return x.t<y.t;
	}
	return x.x<y.x;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n,ans=inf;
	cin>>n;
	for(int i=1;i<=n;i++){
		ll l,r,t;
		cin>>l>>r>>t;
		a[i*2-1]={l,t};
		a[i*2]={r,t};
	}
	n=n*2;
	sort(a+1,a+1+n,cmp);
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			dp[i][j][0]=inf;
			dp[i][j][1]=inf;
		}
	}
	dp[1][n][0]=max(a[1].x,a[1].t);
	dp[1][n][1]=max(a[n].x,a[n].t);
	for(int len=n;len>=1;len--){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			if(i-1>=1){
				dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+a[i].x-a[i-1].x);
				dp[i][j][1]=min(dp[i][j][1],dp[i-1][j][0]+a[j].x-a[i-1].x);
			}
			if(j+1<=n){
				dp[i][j][1]=min(dp[i][j][1],dp[i][j+1][1]+a[j+1].x-a[j].x);
				dp[i][j][0]=min(dp[i][j][0],dp[i][j+1][1]+a[j+1].x-a[i].x);
			}
			dp[i][j][0]=max(dp[i][j][0],a[i].t);
			dp[i][j][1]=max(dp[i][j][1],a[j].t);
			if(len==1){
				ans=min(ans,min(dp[i][j][1],dp[i][j][0]));
			}
		}
	}
	cout<<ans<<"\n";
	return 0;
}

正解代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5005;
const ll inf=LONG_LONG_MAX;
ll dp[2*N][2],p[2*N][2];
struct node{
	ll x,t;
}a[2*N];
bool cmp(node x,node y){
	if(x.x==y.x){
		return x.t<y.t;
	}
	return x.x<y.x;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n,ans=inf;
	cin>>n;
	for(int i=1;i<=n;i++){
		ll l,r,t;
		cin>>l>>r>>t;
		a[i*2-1]={l,t};
		a[i*2]={r,t};
	}
	n=n*2;
	sort(a+1,a+1+n,cmp);
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			dp[i][0]=inf;
			dp[i][1]=inf;
		}
	}
	dp[1][0]=max(a[1].x,a[1].t);
	dp[1][1]=max(a[n].x,a[n].t);
	for(int len=n;len>=1;len--){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			if(i-1>=1){
				dp[i][0]=min(dp[i][0],p[i-1][0]+a[i].x-a[i-1].x);
				dp[i][1]=min(dp[i][1],p[i-1][0]+a[j].x-a[i-1].x);
			}
			if(j+1<=n){
				dp[i][1]=min(dp[i][1],p[i][1]+a[j+1].x-a[j].x);
				dp[i][0]=min(dp[i][0],p[i][1]+a[j+1].x-a[i].x);
			}
			dp[i][0]=max(dp[i][0],a[i].t);
			dp[i][1]=max(dp[i][1],a[j].t);
			if(len==1){
				ans=min(ans,min(dp[i][1],dp[i][0]));
			}
		}
		for(int i=1;i<=n;i++){
			p[i][0]=dp[i][0];
			p[i][1]=dp[i][1];
			dp[i][0]=inf;
			dp[i][1]=inf;
		}
	}
	cout<<ans<<"\n";
	return 0;
}