P2339 Turning in Homework

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

/*
题意：走廊上有 C 个教室，第 i 个坐标为 x_i，老师最早 t_i 接收作业。
      派大星从 0 出发，速率 1，每交完一门才可走，最后必须走到 B 离开。
      求最早离开时间。

做法：经典区间 DP。
f[l][r][0]：区间 [l,r] 尚未交，当前位置在 l（刚交完 l-1）所需最早时刻
f[l][r][1]：同理，当前位置在 r（刚交完 r+1）

先把区间设为 [1,C]，每次只缩外层（一定优于先缩内部）。
转移时记录“走到下一端 + 等待老师”的最小完工时刻。
长度从大到小递推，最后区间缩成单点 [i,i]，再加 |x_i-B| 取最小即可。
复杂度 O(C²)，C≤1000 轻松通过。
*/

const int N=1005;
const ll INF=4e18;

struct P{int x,t;} a[N];
ll f[N][N][2];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int c,h,B;
    if(!(cin>>c>>h>>B)) return 0;
    for(int i=1;i<=c;i++) cin>>a[i].x>>a[i].t;

    sort(a+1,a+c+1,[](P A,P B){return A.x==B.x?A.t<B.t:A.x<B.x;});

    for(int i=0;i<=c+1;i++)
        for(int j=0;j<=c+1;j++)
            f[i][j][0]=f[i][j][1]=INF;

    f[1][c][0]=max<ll>(a[1].x,a[1].t);
    f[1][c][1]=max<ll>(a[c].x,a[c].t);

    for(int d=c-2;d>=0;d--)          // 区间长度
        for(int l=1;l+d<=c;l++){
            int r=l+d;

            // 更新 f[l][r][0]（站在 l）
            ll v=INF;
            if(l>1)   v=min(v,f[l-1][r][0]+(ll)(a[l].x-a[l-1].x));
            if(r<c)   v=min(v,f[l][r+1][1]+(ll)(a[r+1].x-a[l].x));
            f[l][r][0]=max(v,(ll)a[l].t);

            // 更新 f[l][r][1]（站在 r）
            v=INF;
            if(r<c)   v=min(v,f[l][r+1][1]+(ll)(a[r+1].x-a[r].x));
            if(l>1)   v=min(v,f[l-1][r][0]+(ll)(a[r].x-a[l-1].x));
            f[l][r][1]=max(v,(ll)a[r].t);
        }

    ll ans=INF;
    for(int i=1;i<=c;i++){
        ll best=min(f[i][i][0],f[i][i][1]);
        ans=min(ans,best+abs(a[i].x-B));
    }
    cout<<ans<<'\n';
    return 0;
}