2017 acm

注意到若有连续的若干个教室$[l,r]$ 均没交作业，那么下一步最优的做法仅可能先到两端（$l$ 或$r$ ）（若先到中间，则必然会折返回来，而这部分时间花费实际是不必要的）。

故可以定义状态$dp[i][j][0]$ 表示当前在位置$i$ ，$(i,j]$ 间的教室作业都没交的最小花费；$dp[i][j][1]$ 表示当前在位置$i$ ，$[i,j)$ 间的教室作业都没交的最小花费。

复杂度$O(n^2)$ 。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1000+5;
const ll inf=1e15;
ll c,h,b,dp[N][N][2];
struct node{
    ll p,t;
    friend bool operator<(node a,node b){
        return a.p<b.p;
    }
}a[N];
ll Abs(ll x){return x>0?x:-x;}
ll Max(ll x,ll y){return x>y?x:y;}
ll Min(ll x,ll y){return x<y?x:y;}
ll solve(ll l,ll r,ll op){
    if(l<0||r>=c)return inf;
    if(dp[l][r][op]!=-1)return dp[l][r][op];
    if(op==0){
        dp[l][r][op]=Min(Max(solve(l-1,r,0)+Abs(a[l-1].p-a[l].p),a[l].t),Max(solve(l,r+1,1)+Abs(a[r+1].p-a[l].p),a[l].t));
    }else{
        dp[l][r][op]=Min(Max(solve(l-1,r,0)+Abs(a[l-1].p-a[r].p),a[r].t),Max(solve(l,r+1,1)+Abs(a[r+1].p-a[r].p),a[r].t));
    }
    return dp[l][r][op];
}
int main(void){
    scanf("%lld%lld%lld",&c,&h,&b);
    for(int i=0;i<c;++i)scanf("%lld%lld",&a[i].p,&a[i].t);
    sort(a,a+c);
    memset(dp,-1,sizeof(dp));
    dp[0][c-1][0]=Max(a[0].p,a[0].t);
    dp[0][c-1][1]=Max(a[c-1].p,a[c-1].t);
    ll ans=inf;
    for(int i=0;i<c;++i)
        ans=Min(ans,solve(i,i,0)+Abs(a[i].p-b));
    printf("%lldn",ans);
}