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