#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; struct node { int x,t; }edge[1005]; int cmp(node a,node b) { return a.x<b.x; } int c,h,b; int f[1005][1005][2]; int main() { scanf("%d %d %d",&c,&h,&b); for(int i=1;i<=c;i++) { scanf("%d %d",&edge[i].x,&edge[i].t); } sort(edge+1,edge+1+c,cmp); memset(f,0x3f,sizeof(f)); f[1][c][0]=max(edge[1].x,edge[1].t); f[1][c][1]=max(edge[c].x,edge[c].t); for(int i=1;i<=c;i++) { for(int j=c;j>=i;j--) { if(i==1&&j==c)continue; if(i==1) { f[i][j][0]=max(f[i][j+1][1]+edge[j+1].x-edge[i].x,edge[i].t); f[i][j][1]=max(f[i][j+1][1]+edge[j+1].x-edge[j].x,edge[j].t); }else if(j==h) { f[i][j][0]=max(f[i-1][j][0]+edge[i].x-edge[i-1].x,edge[i].t); f[i][j][1]=max(f[i-1][j][0]+edge[j].x-edge[i-1].x,edge[j].t); }else { f[i][j][0]=min(max(f[i-1][j][0]+edge[i].x-edge[i-1].x,edge[i].t),max(f[i][j+1][1]+edge[j+1].x-edge[i].x,edge[i].t)); f[i][j][1]=min(max(f[i-1][j][0]+edge[j].x-edge[i-1].x,edge[j].t),max(f[i][j+1][1]+edge[j+1].x-edge[j].x,edge[j].t)); } } } int ans=0x3f3f3f3f; for(int i=1;i<=c;i++) { ans=min(ans,min(f[i][i][0]+abs(edge[i].x-b),f[i][i][1]+abs(edge[i].x-b))); } printf("%d",ans); } |
Double click to view unformatted code.