UVA-1025 A Spy in the Metro(多決策dp)

​​UVA-1025 A Spy in the Metro​​

題目

某城市的地鐵是線性的，有n（2≤n≤50）個車站，從左到右編号為1～n。有M1輛列車從第1站開始往右開，還有M2輛列車從第n站開始往左開。在時刻0，Mario從第1站出發，目的是在時刻T（0≤T≤200）會見車站n的一個間諜。在車站等車時容易被抓，是以她決定盡量躲在開動的火車上，讓在車站等待的總時間盡量短。列車靠站停車時間忽略不計，且Mario身手靈活，即使兩輛方向不同的列車在同一時間靠站，Mario也能完成換乘。

輸入第1行為n，第2行為T，第3行有n－1個整數表示地鐵從車站i到i＋1的行駛時間（兩個方向一樣）。第4行為M1（1≤M1≤50），即從第1站出發向右開的列車數目。第5行包含M1個整數d1, d2,…, dM1（0≤di≤250，di＜di+1），即各列車的出發時間。第6、7行描述從第n站出發向左開的列車，格式同第4、5行。輸出僅包含一行，即最少等待時間。無解輸出impossible。

分析

按照時間流逝，定義狀态（i, j），表示時刻 i，到達 j站台。

先預處理0到T時間裡，每個列車所處的狀态，如果 i 時刻剛好到達 j 站，那麼我們說（i， j）有向左/右的列車。這是為後面dp準備。

dp階段，定義dp[i][j] 表示再時刻 i，你在車站 j 最少還要等多少時間。

由題意知：dp[T][n] = 0; 因為T時刻要求到達n站台。

對于其他狀态，有三種決策，要選擇最優決策：

1. 等一個機關時間
2. 搭成向右開的車（如果存在）
3. 搭成向左開的車（如果存在）

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e2 + 10;

int n, T;
int m1, m2, d, cas = 1;
int dp[N][N];   //dp[i][j] 表示再時刻 i，你在車站 j 最少還要等多少時間
int t[N];               //相鄰車站行駛時間      
int l[N][N], r[N][N];   //在 i時刻，車站j，是否有向左或右開的車

void DP()
{
    for(int i = 1; i <= n-1; i++){
        dp[T][i] = INF;                 //T時刻如果在其他站，就永遠到不了n
    }
    dp[T][n] = 0;                       //T時刻隻能在n站
    for(int i = T-1; i >= 0; i--){      //從時間 T 往前推
        for (int j = 1; j <= n; j++){
            dp[i][j] = dp[i + 1][j] + 1;
            if(j < n && r[i][j] && i+t[j] <= T)
                dp[i][j] = min(dp[i][j], dp[i + t[j]][j + 1]);  //右
            if(j > 1 && l[i][j] && i+t[j-1] <= T)
                dp[i][j] = min(dp[i][j], dp[i + t[j - 1]][j - 1]);//左
        }
    }
}

int main()
{
    while(cin >> n >> T && n){
        for (int i = 1; i <= n-1; i++){
            cin >> t[i];        //每個車站向右邊車站的行駛時間
        }
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));
        cin >> m1;
        while(m1--){    //向右開的列車
            cin >> d;   //對于每個列車，計算到達每個站的時間
            for(int j = 1; j <= n-1; j++){
                if(d <= T)
                    r[d][j] = 1;
                d += t[j];
            }
        }
        cin >> m2;  
        while(m2--){   //向左開的列車 
            cin >> d;
            for (int j = n - 1; j >= 1; j--){
                if(d <= T)
                    l[d][j + 1] = 1;
                d += t[j];
            }
        }
        DP();
        cout << "Case Number " << cas++ << ": ";
        if(dp[0][1] >= INF)
            cout << "impossible\n";
        else
            cout << dp[0][1] << endl;
    }
    return 0;
}