UVA1025 城市里的間諜 A Spy in the Metro

題面翻譯

題目大意

某城市地鐵是一條直線，有 $n$（$2\le n\le 50$）個車站，從左到右編號 $1\dots n$。有 $M_1$ 輛列車從第 $1$ 站開始往右開，還有 $M_2$ 輛列車從第 $n$ 站開始往左開。列車在相鄰站臺間所需的運行時間是固定的，因為所有列車的運行速度是相同的。在時刻 $0$，Mario 從第 $1$ 站出發，目的在時刻 $T$（$0\le T\le 200$）會見車站 $n$ 的一個間諜。在車站等車時容易被抓，所以她決定盡量躲在開動的火車上，讓在車站等待的時間盡量短。列車靠站停車時間忽略不計，且 Mario 身手敏捷，即使兩輛方向不同的列車在同一時間靠站，Mario 也能完成換乘。

輸入格式

輸入文件包含多組數據。

每一組數據包含以下 $7$ 行：

第一行是一個正整數 $n$，表示有 $n$ 個車站。

第二行是為 $T$，表示 Mario 在時刻 $T$ 會見車站 $n$ 的間諜。

第三行有 $n?1$ 個整數 $t_1,t_2,\dots ,t_{n?1}$，其中 $t_i$ 表示地鐵從車站 $i$ 到 $i+1$ 的行駛時間。

第四行為 $M_1$，及從第一站出發向右開的列車數目。

第五行包含 $M_1$ 個正整數 $a_1,a_2,\dots ,a_{M_1}$，即每個列車出發的時間。

第六行為 $M_2$ ，即從第 $n$ 站出發向左開的列車數目。

第七行包含 $M_2$ 個正整數 $b_1,b_2,\dots ,b_{M_2}$，即每個列車出發的時間。

輸入文件以一行 $0$ 結尾。

輸出格式

有若干行，每行先輸出 Case Number XXX : （XXX為情況編號，從 $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，通過逆向遞推建立狀態轉移方程，可以得到以下三種情況

1. dp[i][j]=dp[i+1][j]+1，即dp[i][j] 為在i+1時刻在第j站的所等待的時間+1
2. dp[i][j]=min(dp[i+t[j]][j+1],dp[i][j])，即若第i時刻存在向右開的車，且此時到達下一個站的時間不大于T時，dp[i][j]為第i+t[j]時刻在第j+1站臺所等待的時間與在在這個站臺等待的時間點最小值
3. 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 1000000000using 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) { //若此時向右有車，且到達下一個站的時間不大于Tdp[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) { //若此時向左有車，且到達下一個站的時間不大于Tdp[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;
}