0w1

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;
}