POJ 2374 Fence Obstacle Course

DP+线段树
View Code
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 #define lson l, m, rt << 1
  7 #define rson m + 1, r, rt << 1 | 1
  8 
  9 using namespace std;
 10 
 11 const int MAXN = 100000;
 12 const int MAXSIZE = MAXN << 1;
 13 const int INF = 2147483645;
 14 
 15 struct Fence
 16 {
 17     int st, ed;
 18 };
 19 
 20 int N, S;
 21 Fence F[ MAXN + 10 ];
 22 int up[ ( MAXSIZE << 2 ) + 10 ], flag[ ( MAXSIZE << 2 ) + 10 ];
 23 int dp[50010][2];
 24 int MinBound, MaxBound;
 25 
 26 void PushDown( int rt )
 27 {
 28     int lc = rt << 1;
 29     int rc = rt << 1 | 1;
 30     if ( flag[rt] != -1 )
 31     {
 32         flag[lc] = flag[rc] = flag[rt];
 33         up[lc] = up[rc] = flag[rt];
 34         flag[rt] = -1;
 35     }
 36     return;
 37 }
 38 
 39 void Update( int L, int R, int c, int l, int r, int rt )
 40 {
 41     if ( L <= l && r <= R )
 42     {
 43         up[rt] = c;
 44         flag[rt] = c;
 45         return;
 46     }
 47     PushDown( rt );
 48 
 49     int m = ( l + r ) >> 1;
 50     if ( L <= m ) Update( L, R, c, lson );
 51     if ( R > m ) Update( L, R, c, rson );
 52 
 53     return;
 54 }
 55 
 56 int Query( int L, int l, int r, int rt )
 57 {
 58     if ( L == l && L == r )
 59     {
 60         return up[rt];
 61     }
 62     PushDown(rt);
 63 
 64     int m = ( l + r ) >> 1;
 65     if ( L <= m ) return Query( L, lson );
 66     else return Query( L, rson );
 67 }
 68 
 69 void Solved()
 70 {
 71     memset( dp[0], 0, sizeof(dp[0]) );
 72 
 73     for ( int i = 1; i <= N; ++i )
 74     {
 75         int left = Query( F[i].st, MinBound, MaxBound, 1 );
 76         int right = Query( F[i].ed, MinBound, MaxBound, 1 );
 77         //printf( "left=%d right=%d\n", left, right );
 78 
 79         dp[i][0] = min( dp[left][0] + abs( F[left].st - F[i].st ) , dp[left][1] + abs( F[left].ed - F[i].st ) );
 80         dp[i][1] = min( dp[right][0] + abs( F[right].st - F[i].ed ) , dp[right][1] + abs( F[right].ed - F[i].ed ) );
 81 
 82         Update( F[i].st, F[i].ed, i, MinBound, MaxBound, 1 );
 83     }
 84 
 85     int ans = min( dp[N][0] + abs( F[N].st - S - MAXN ), dp[N][1] + abs( F[N].ed - S - MAXN ) );
 86     printf( "%d\n", ans );
 87 
 88     return;
 89 }
 90 
 91 int main()
 92 {
 93     while ( ~scanf( "%d%d", &N, &S ) )
 94     {
 95         MinBound = INF;
 96         MaxBound = -1;
 97 
 98         F[0].st = 0 + MAXN;
 99         F[0].ed = 0 + MAXN;
100 
101         for ( int i = 1; i <= N; ++i )
102         {
103             scanf( "%d%d", &F[i].st, &F[i].ed );
104             F[i].st += MAXN;
105             F[i].ed += MAXN;
106             MinBound = min( MinBound, F[i].st );
107             MaxBound = max( MaxBound, F[i].ed );
108         }
109 
110         memset( up, 0, sizeof(up) );
111         memset( flag, -1, sizeof(flag) );
112 
113         Solved();
114     }
115     return 0;
116 }