UVA 1025 A Spy in the Metro DP

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; int n, t, times[100], m1, m2; int has_train[1000][1000][2]; int dp[1000][1000]; int main() { int kase = 0; while (scanf("%d", &n) == 1 && n) { memset(times, 0, sizeof(times)); memset(has_train, 0, sizeof(has_train)); memset(dp, 0, sizeof(dp)); scanf("%d", &t); for (int i = 1; i < n; i++) scanf("%d", ×[i]); scanf("%d", &m1); for (int i = 1; i <= m1; i++) { int temp; scanf("%d", &temp); for (int j = 1; j <= n; j++) { has_train[temp][j][0] = 1; temp += times[j]; } } scanf("%d", &m2); for (int i = 1; i <= m2; i++) { int temp; scanf("%d", &temp); for (int j = n; j >= 1; j--) { has_train[temp][j][1] = 1; temp += times[j-1]; } } for (int i = 1; i <= n - 1; 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 + times[j] <= t) { dp[i][j] = min(dp[i][j], dp[i + times[j]][j + 1]); } if (j > 1 && has_train[i][j][1] && i + times[j-1] <= t) { dp[i][j] = min(dp[i][j], dp[i + times[j-1]][j-1]); } } } cout << "Case Number " << ++kase << ": "; if (dp[0][1] >= INF) cout << "impossible\n"; else cout << dp[0][1] << endl; } return 0; }