题意：





思路：

考虑DP

先把事件按照地点顺序排个序

f[i][j][0]表示从i到j还没有去过 现在在i

f[i][j][1]表示从i到j还没有去过 现在在j

那么方程就呼之欲出了

f[i][j][0]=max(min(f[i-1][j][0]+node[i].pos-node[i-1].pos,f[i][j+1][1]+node[j+1].pos-node[i].pos),node[i].t);

f[i][j][1]=max(min(f[i-1][j][0]+node[j].pos-node[i-1].pos,f[i][j+1][1]+node[j+1].pos-node[j].pos),node[j].t);

需要对边界进行特殊处理

//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

int n,h,b,f[1005][1005][2];

struct Node{int pos,t;}node[1005];

bool cmp(Node a,Node b){if(a.pos!=b.pos)return a.pos<b.pos;return a.t<b.t;}

int main(){

    scanf("%d%d%d",&n,&h,&b);

    for(int i=1;i<=n;i++)scanf("%d%d",&node[i].pos,&node[i].t);

    node[++n].pos=b,n++;

    sort(node+1,node+1+n,cmp);

    for(int i=1;i<=n;i++)

        for(int j=n;j>=i;j--){

                if(i==1&&j==n){f[i][j][1]=max(node[j].t,node[j].pos);continue;}

                if(i==1){

                    f[i][j][0]=max(f[i][j+1][1]+node[j+1].pos-node[i].pos,node[i].t);

                    f[i][j][1]=max(f[i][j+1][1]+node[j+1].pos-node[j].pos,node[j].t);

                    continue;

                }

                if(j==n){

                    f[i][j][0]=max(f[i-1][j][0]+node[i].pos-node[i-1].pos,node[i].t);

                    f[i][j][1]=max(f[i-1][j][0]+node[j].pos-node[i-1].pos,node[j].t);

                    continue;

                }

                f[i][j][0]=max(min(f[i-1][j][0]+node[i].pos-node[i-1].pos,f[i][j+1][1]+node[j+1].pos-node[i].pos),node[i].t);

                f[i][j][1]=max(min(f[i-1][j][0]+node[j].pos-node[i-1].pos,f[i][j+1][1]+node[j+1].pos-node[j].pos),node[j].t);

        }

    for(int i=1;i<=n;i++)if(node[i].pos==b){printf("%d\n",min(f[i][i][0],f[i][i][1]));return 0;}

}