UVA 1025 A Spy in the Metro ( DP )
UVa Online Judge
令 dp( i, j ) 為時間點 i時在車站 j時的最短等待時間,邊界 dp( T, n ) = 0。另外預處理 hasTrain[ k ][ i ][ j ] 車站 j在時間點 i是否有往左 / 右的火車。
#include <bits/stdc++.h> using namespace std; const int MAXT = 200 + 2; const int MAXN = 50 + 5; const int INF = 1e9; int cost[MAXN], deptime[2][MAXN]; bool hasTrain[2][MAXT][MAXN]; int memo[MAXT][MAXN]; int main(){ ios::sync_with_stdio(false); int kase = 0; int n, t, m1, m2; while( cin >> n && n ){ memset( hasTrain, false, sizeof(hasTrain) ); cin >> t; for(int i = 1; i < n; ++i) cin >> cost[i]; cin >> m1; for(int i = 0; i < m1; ++i){ cin >> deptime[0][i]; int cur_time = deptime[0][i]; for(int j = 1; j < n; ++j){ if( cur_time > t ) break; hasTrain[0][cur_time][j] = true; cur_time += cost[j]; } } cin >> m2; for(int i = 0; i < m2; ++i){ cin >> deptime[1][i]; int cur_time = deptime[1][i]; for(int j = n; j > 1; --j){ if( cur_time > t ) break; hasTrain[1][cur_time][j] = true; cur_time += cost[j - 1]; } } for(int i = 1; i < n; ++i) memo[t][i] = INF; memo[t][n] = 0; for(int i = t - 1; i >= 0; --i) for(int j = 1; j <= n; ++j){ memo[i][j] = memo[i + 1][j] + 1; // wait if( j < n && hasTrain[0][i][j] && i + cost[j] <= t ) memo[i][j] = min( memo[i][j], memo[i + cost[j]][j + 1] ); if( j > 1 && hasTrain[1][i][j] && i + cost[j - 1] <= t ) memo[i][j] = min( memo[i][j], memo[i + cost[j-1]][j - 1] ); } cout << "Case Number " << ++kase << ": "; if( memo[0][1] >= INF ) cout << "impossible" << endl; else cout << memo[0][1] << endl; } return 0; }