题意分析

贝茜需要在一条长度为H的走廊上提交C份作业，每个作业有指定的提交位置和老师的最早接收时间。她初始位于走廊起点（0米处），行走速度为1米/秒，可以按任意顺序提交作业。提交作业不耗时，但必须等到老师允许的时间才能提交。最后，她需要到达走廊上的某个指定位置B（巴士等待区出口）。求她完成所有提交并到达出口的最早时间。

关键点

行走时间：贝茜的移动速度固定（1米/秒），行走时间=移动距离。

提交时间限制：到达教室后，如果时间早于老师的最早接收时间，必须等待。

最优顺序：需要选择最优的作业提交顺序，使得总时间最短。

最终目标：提交所有作业后，从最后一个教室走到出口B。

解题思路

1.问题性质 这是一个典型的动态规划（DP）问题，涉及时间最优化和路径规划。

由于贝茜可以自由选择提交顺序，且提交顺序会影响总时间，因此需要区间DP来覆盖所有可能的路径组合。

2. 动态规划设计 状态定义： $dp[l][r][k]$ 表示已经提交了从第$l$到第$r$个教室（按位置排序后）的作业，当前位于左端点$（k=0）$或右端点$（k=1）$时的最小时间。

状态转移：

如果当前在左端点$l$，可以从$l+1$或$r$走过来：

从$l+1$走到$l$：$时间 = dp[l+1][r][0] + (pos[l+1] - pos[l])$

$实际提交时间 = max(到达时间, 老师接收时间)$。

从$r$走到$l$：$时间 = dp[l+1][r][1] + (pos[r] - pos[l])$

实际提交时间同理。

如果当前在右端点r，可以从l或r-1走过来，类似上述逻辑。

初始化：

$单个教室i：dp[i][i][0] = dp[i][i][1] = max(pos[i], t[i])$（走到教室并等待）。

最终答案：

遍历所有可能的最后一个教室位置i，计算$min(dp[0][C-1][0] + |pos[0]-B|$,$dp[0][C-1][1] + |pos[C-1] - B|)$。

3. 算法步骤

排序：将所有教室按位置升序排序。

初始化DP表：处理单个教室的情况。

区间DP：按区间长度从小到大递推，更新左右端点的状态。

计算答案：结合最后一个教室的位置和出口B的距离。

4. 复杂度分析

时间复杂度：O(C²)，适用于C ≤ 1,000。

空间复杂度：O(C²)。

代码实现

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1005
#define INF 10000005
int dp[N][N][2];
struct node
{
    int x;
    int t;
} a[N];
int cmp(node a,node b)
{
    if(a.x==b.x)
        return a.t<b.t;
    return a.x<b.x;
}
void DP(int n)
{
//大区间推出小区间
    dp[1][n][0] = max(a[1].x, a[1].t);
    dp[1][n][1] = max(a[n].x, a[n].t);
    for(int d=n-2; d>=0; d--)
    {
        for(int i=1; i+d<=n; i++)
        {
            int s=i;
            int e=i+d;
            dp[s][e][0]=INF;

            if(s-1>0)
            {
                dp[s][e][0]=min(dp[s][e][0],dp[s-1][e][0]+a[s].x-a[s-1].x);
            }
            if(e+1<=n)
            {
                dp[s][e][0]=min(dp[s][e][0],dp[s][e+1][1]+a[e+1].x-a[s].x);
            }
            if(dp[s][e][0]<a[s].t)
                dp[s][e][0]=a[s].t;
            
            dp[s][e][1]=INF;
            if(e+1<=n)
            {
                dp[s][e][1]=min(dp[s][e][1],dp[s][e+1][1]+a[e+1].x-a[e].x);
            }
            if(s-1>0)
            {
                dp[s][e][1]=min(dp[s][e][1],dp[s-1][e][0]+a[e].x-a[s-1].x);
            }
            if(dp[s][e][1]<a[e].t)
                dp[s][e][1]=a[e].t;
            
        }
    }
}
int main()
{
    int C,H,B;
    scanf("%d%d%d",&C,&H,&B);
    for(int i=1; i<=C; i++)
    {
        scanf("%d%d",&a[i].x,&a[i].t);
    }
    sort(a+1,a+C+1,cmp);

    a[0].x=0;
    a[0].t=0;
    DP(C);
    int ans=INF;
    
    for(int i=1; i<=C; i++)
    {
        ans=min(min(dp[i][i][0]+abs(a[i].x-B),dp[i][i][1]+abs(a[i].x-B)),ans);
    }
    printf("%d\n",ans);
    return 0;
}