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……

 #include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm> #define LL long long int using namespace std; const int MAXN = ;
const LL INF = (LL) << ; struct Team
{
int id;
LL pos;
}; LL dp[][MAXN];
Team peo[MAXN];
Team shlt[MAXN];
int N, M;
bool path[MAXN][MAXN];
int ans[MAXN], getJ; bool cmp( Team a, Team b )
{
if ( a.pos != b.pos ) return a.pos < b.pos;
return a.id < b.id;
} LL DP()
{
int pre = , cur = ; for ( int i = ; i <= N; ++i )
{
if ( N - i >= M - )
dp[][i] = dp[][i - ] + abs( peo[i].pos - shlt[].pos );
else dp[][i] = INF;
}
dp[][] = ; for ( int i = ; i <= M; ++i )
{
pre ^= ;
cur ^= ;
for ( int j = i; j <= N; ++j )
{
dp[cur][j] = dp[pre][j - ] + abs( peo[j].pos - shlt[i].pos );
path[i][j] = true; if ( j > i && dp[cur][j - ] + abs( peo[j].pos - shlt[i].pos ) < dp[cur][j] )
{
dp[cur][j] = dp[cur][j - ] + abs( peo[j].pos - shlt[i].pos );
path[i][j] = false; } }
}
return dp[cur][N];
} void PrintPath( int i, int j )
{
if ( i == )
{
getJ = j;
return;
} switch ( path[i][j] )
{
case false:
PrintPath( i, j - );
break;
case true:
PrintPath( i - , j - );
break;
} ans[ peo[j].id ] = shlt[i].id; return;
} int main()
{
while ( ~scanf( "%d", &N ) )
{
for ( int i = ; i <= N; ++i )
{
scanf( "%lld", &peo[i].pos );
peo[i].id = i;
}
sort( peo + , peo + N + , cmp ); scanf( "%d", &M );
for ( int j = ; j <= M; ++j )
{
scanf( "%lld", &shlt[j].pos );
shlt[j].id = j;
}
sort( shlt + , shlt + M + , cmp ); printf( "%lld\n", DP() );
PrintPath( M, N );
while ( getJ > )
{
ans[ peo[ getJ ].id ] = shlt[].id;
--getJ;
} for ( int i = ; i <= N; ++i )
{
if ( i != ) putchar(' ');
printf( "%d", ans[i] );
}
puts("");
}
return ;
}
上一篇:Spring + iBATIS完整示例


下一篇:[Heroku] How to pull, push changes