A Spy in the Metro

UVA1025
定义： $dp[i][j]$为在第 $i$时刻间谍到达第j个车站时在车站待的最短时间, $RightTrain[i][j]$表示在第 $i$时刻是否有从左向右开的列车， $LeftTrain[i][j]$同理。
初始化： $dp[0][1]=0$,剩下的dp元素 $=inf$
转移方程：
在第 $i$时刻间谍位于第 $j$个车站时有三种转移方式：

1. 由第 $i-1$时刻在第 $j$个站台等待 $1$个时刻
2. 上一次在 $j$站台左边的站台并且搭上从左往右开的列车到达 $j$站台
3. 上一次在 $j$站台右边的站台并且搭上从右往左开的列车到达 $j$站台

dp[i][j] = dp[i - 1][j] + 1;//对应1。
if (RightTrain[i][j]) {//对应2.
dp[i][j] = min(dp[i][j], dp[i - Time[j - 1]][j - 1]);
}
if (LeftTrain[i][j]) {//对应3.
dp[i][j] = min(dp[i][j], dp[i - Time[j]][j + 1]);
}		

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[201][51], Time[51];
bool RightTrain[201][51], LeftTrain[201][51];
int n, T;
constexpr static int inf = 0x3f3f3f3f;
bool Input() {memset(LeftTrain, false, sizeof(LeftTrain));memset(RightTrain, false, sizeof(RightTrain));cin >> n;if (!n) {return false;}cin >> T;for (int i = 1; i <= n - 1; ++i) {cin >> Time[i];}Time[n] = 0;int M;cin >> M;while (M--) {int StartTime;cin >> StartTime;RightTrain[StartTime][1] = true;for (int i = 2; i <= n; ++i) {StartTime += Time[i - 1];if (StartTime > T) {break;}RightTrain[StartTime][i] = true;}}cin >> M;while (M--) {int StartTime;cin >> StartTime;LeftTrain[StartTime][n] = true;for (int i = n - 1; i >= 1; --i) {StartTime += Time[i];if (StartTime > T) {break;}LeftTrain[StartTime][i] = true;}}return true;
}
int DP() {memset(dp, 0x3f, sizeof(dp));dp[0][1] = 0;for (int i = 1; i <= T; ++i) {for (int j = 1; j <= n; ++j) {dp[i][j] = dp[i - 1][j] + 1;if (RightTrain[i][j]) {dp[i][j] = min(dp[i][j], dp[i - Time[j - 1]][j - 1]);}if (LeftTrain[i][j]) {dp[i][j] = min(dp[i][j], dp[i - Time[j]][j + 1]);}		}}return dp[T][n];
}
int main() {ios::sync_with_stdio(false);int Case = 0;while (Input()) {int&& Ans = DP();cout << "Case Number " << ++Case << ": ";if (Ans >= inf) {cout << "impossible" << endl;}else {cout << Ans << endl;}}return 0;
}