HDU 3757 Evacuation Plan DP

跟 UVa 1474 - Evacuation Plan 一个题，但是在杭电上能交过，在UVa上交不过……不知道哪里有问题……

将施工队位置和避难所位置排序。

dp[i][j] 代表前 i 个避难所收留前 j 个施工队。

dp[i][j] = min( dp[i - 1][j - 1], dp[i][j - 1] ) + abs( b[i] - a[j] );

内存卡的比较死，要用滚动数组，并且记录路径的path[i][j]只能用bool型。MLE了四五次OTL……

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 #define LL long long int
  7 
  8 using namespace std;
  9 
 10 const int MAXN = 4010;
 11 const LL INF = (LL)1 << 50;
 12 
 13 struct Team
 14 {
 15     int id;
 16     LL pos;
 17 };
 18 
 19 LL dp[2][MAXN];
 20 Team peo[MAXN];
 21 Team shlt[MAXN];
 22 int N, M;
 23 bool path[MAXN][MAXN];
 24 int ans[MAXN], getJ;
 25 
 26 bool cmp( Team a, Team b )
 27 {
 28     if ( a.pos != b.pos ) return a.pos < b.pos;
 29     return a.id < b.id;
 30 }
 31 
 32 LL DP()
 33 {
 34     int pre = 0, cur = 1;
 35 
 36     for ( int i = 1; i <= N; ++i )
 37     {
 38         if ( N - i >= M - 1 )
 39             dp[1][i] = dp[1][i - 1] + abs( peo[i].pos - shlt[1].pos );
 40         else dp[1][i] = INF;
 41     }
 42     dp[1][0] = 0;
 43 
 44     for ( int i = 2; i <= M; ++i )
 45     {
 46         pre ^= 1;
 47         cur ^= 1;
 48         for ( int j = i; j <= N; ++j )
 49         {
 50             dp[cur][j] = dp[pre][j - 1] + abs( peo[j].pos - shlt[i].pos );
 51             path[i][j] = true;
 52 
 53             if ( j > i && dp[cur][j - 1] + abs( peo[j].pos - shlt[i].pos ) < dp[cur][j] )
 54             {
 55                 dp[cur][j] = dp[cur][j - 1] + abs( peo[j].pos - shlt[i].pos );
 56                 path[i][j] = false;
 57                 
 58             }
 59             
 60         }
 61     }
 62     return dp[cur][N];
 63 }
 64 
 65 void PrintPath( int i, int j )
 66 {
 67     if ( i == 1 )
 68     {
 69         getJ = j;
 70         return;
 71     }
 72 
 73     switch ( path[i][j] )
 74     {
 75     case false:
 76         PrintPath( i, j - 1 );
 77         break;
 78     case true:
 79         PrintPath( i - 1, j - 1 );
 80         break;
 81     }
 82 
 83     ans[ peo[j].id ] = shlt[i].id;
 84 
 85     return;
 86 }
 87 
 88 int main()
 89 {
 90     while ( ~scanf( "%d", &N ) )
 91     {
 92         for ( int i = 1; i <= N; ++i )
 93         {
 94             scanf( "%lld", &peo[i].pos );
 95             peo[i].id = i;
 96         }
 97         sort( peo + 1, peo + N + 1, cmp );
 98 
 99         scanf( "%d", &M );
100         for ( int j = 1; j <= M; ++j )
101         {
102             scanf( "%lld", &shlt[j].pos );
103             shlt[j].id = j;
104         }
105         sort( shlt + 1, shlt + M + 1, cmp );
106 
107         printf( "%lld
", DP() );
108         PrintPath( M, N );
109         while ( getJ > 0 )
110         {
111             ans[ peo[ getJ ].id ] = shlt[1].id;
112             --getJ;
113         }
114 
115         for ( int i = 1; i <= N; ++i )
116         {
117             if ( i != 1 ) putchar(' ');
118             printf( "%d", ans[i] );
119         }
120         puts("");
121     }
122     return 0;
123 }