UVA1025城市里的间谍ASpyintheMetro

UVA1025 城市里的间谍 A Spy in the Metro 题面翻译 题目大意

某城市地铁是一条直线，有 n n n（ 2 ≤ n ≤ 50 2\leq n\leq 50 2≤n≤50）个车站，从左到右编号 1 … n 1\ldots n 1…n。有 M 1 M_1 M1​ 辆列车从第 1 1 1 站开始往右开，还有 M 2 M_2 M2​ 辆列车从第 n n n 站开始往左开。列车在相邻站台间所需的运行时间是固定的，因为所有列车的运行速度是相同的。在时刻 0 0 0，Mario 从第 1 1 1 站出发，目的在时刻 T T T（ 0 ≤ T ≤ 200 0\leq T\leq 200 0≤T≤200）会见车站 n n n 的一个间谍。在车站等车时容易被抓，所以她决定尽量躲在开动的火车上，让在车站等待的时间尽量短。列车靠站停车时间忽略不计，且 Mario 身手敏捷，即使两辆方向不同的列车在同一时间靠站，Mario 也能完成换乘。

输入格式

输入文件包含多组数据。

每一组数据包含以下 7 7 7 行：

第一行是一个正整数 n n n，表示有 n n n 个车站。

第二行是为 T T T，表示 Mario 在时刻 T T T 会见车站 n n n 的间谍。

第三行有 n − 1 n-1 n−1 个整数 t 1 , t 2 , … , t n − 1 t_1,t_2,\ldots,t_{n-1} t1​,t2​,…,tn−1​，其中 t i t_i ti​ 表示地铁从车站 i i i 到 i + 1 i+1 i+1 的行驶时间。

第四行为 M 1 M_1 M1​，及从第一站出发向右开的列车数目。

第五行包含 M 1 M_1 M1​ 个正整数 a 1 , a 2 , … , a M 1 a_1,a_2,\ldots,a_{M_1} a1​,a2​,…,aM1​​，即每个列车出发的时间。

第六行为 M 2 M_2 M2​ ，即从第 n n n 站出发向左开的列车数目。

第七行包含 M 2 M_2 M2​ 个正整数 b 1 , b 2 , … , b M 2 b_1,b_2,\ldots,b_{M_2} b1​,b2​,…,bM2​​，即每个列车出发的时间。

输入文件以一行 0 0 0 结尾。

输出格式

有若干行，每行先输出 Case Number XXX : （XXX为情况编号，从 1 1 1 开始），再输出最少等待时间或 impossible（无解）。

题目描述

PDF

输入格式 输出格式 样例 #1 样例输入 #1 4 55 5 10 15 4 0 5 10 20 4 0 5 10 15 4 18 1 2 3 5 0 3 6 10 12 6 0 3 5 7 12 15 2 30 20 1 20 7 1 3 5 7 11 13 17 0 样例输出 #1 Case Number 1: 5 Case Number 2: 0 Case Number 3: impossible Solution

采用动态规划算法

设dp[i][j]代表第i时刻到在第j站的等待的时间，因为要在T时间内达到第n站，且要求尽可能多的时间在地铁上度过，由此可以知要求dp[T][n]=0，通过逆向递推建立状态转移方程，可以得到以下三种情况

dp[i][j]=dp[i+1][j]+1，即dp[i][j] 为在i+1时刻在第j站的所等待的时间+1dp[i][j]=min(dp[i+t[j]][j+1],dp[i][j])，即若第i时刻存在向右开的车，且此时到达下一个站的时间不大于T时，dp[i][j]为第i+t[j]时刻在第j+1站台所等待的时间与在在这个站台等待的时间点最小值dp[i][j]=min(dp[i+t[j-1]][j-1],dp[i][j])，即若第i时刻存在向左开的车，且此时到达下一个站的时间不大于T时，dp[i][j]为第i+t[j-1]时刻在第j-1站台所等待的时间与在在这个站台等待的时间点最小值

然后最终等待时间为dp[0][1]，即在0时刻在1站台时等待的时间

// // Created by Gowi on 2023/11/23. // #include <iostream> #include <cstring> #define maxN 100 #define MaxT 300 #define INF 1000000000 using namespace std; int T, t[maxN], a[maxN], b[maxN], M1, M2, n; int has_train[MaxT][maxN][2];// has_train[i][j][1/2] i时刻在第j个站是否有向右(0)/左(1)开的火车 int dp[MaxT][maxN]; //dp[i][j]i时刻在第j个站需要等待多长时间 bool init() { int d; cin >> n; if (n == 0) { return false; } memset(t, 0, sizeof(t)); memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(has_train, 0, sizeof(has_train)); memset(dp, 0, sizeof(dp)); cin >> T; for (int i = 1; i < n; ++i) { cin >> t[i]; } cin >> M1; for (int i = 1; i <= M1; ++i) { cin >> a[i]; d = a[i]; for (int j = 1; j < n; ++j) { has_train[d][j][0] = 1; d += t[j]; } } cin >> M2; for (int i = 1; i <= M2; ++i) { cin >> b[i]; d = b[i]; for (int j = n - 1; j > 0; j--) { has_train[d][j+1][1] = 1; d += t[j]; } } return true; } int main() { int k = 0; while (init()) { for (int i = 1; i < n; ++i) { dp[T][i] = INF; } dp[T][n] = 0; for (int i = T - 1; i >= 0; i--) { for (int j = 1; j <= n; ++j) { dp[i][j] = dp[i + 1][j] + 1; // 等待一分钟 if (j < n && has_train[i][j][0] && i + t[j] <= T) { //若此时向右有车，且到达下一个站的时间不大于T dp[i][j] = min(dp[i][j], dp[i + t[j]][j + 1]); //状态转移方程 } if (j > 1 && has_train[i][j][1] && i + t[j-1] <= T) { //若此时向左有车，且到达下一个站的时间不大于T dp[i][j] = min(dp[i][j], dp[i + t[j - 1]][j - 1]); //状态转移方程 } } } cout << "Case Number " << ++k << ": "; if (dp[0][1] >= INF) { cout << "impossible" << endl; } else { cout << dp[0][1] << endl; } } return 0; }