UVA 1025 A Spy in the Metro DP

UVA 1025 A Spy in the Metro DP

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。