UVA 1025 A Spy in the Metro——dp

UVA 1025 A Spy in the Metro——dp

记得当时刚做dp时这道题死活做不出来，现在重新做一遍，也算是消除心理阴影了

经过推理，我们发现当前时刻、当前车站构成了一个状态，而做哪一班车去下一个车站与状态转移密切相关，因此我们定义dp【i】【j】表示间谍在时刻i位于车站j的最小等待时间（进一步思考会发现递推时间时没有后效性的，所以这个状态时正确的），结果就是dp【T】【N】。

在上面状态的基础上我们考虑状态转移，首先确定一点就是每辆车到达每个车站的时刻都是固定的，这个递推一下，保存一下结果就好了，然后考虑当前状态dp【i】【j】应该如何转移（这里用的是刷表法，也就是用当前状态更新其他状态），具体情况如下：

1.在这个车站等待1个单位时间

2.如果当前时刻下恰好有地铁k停留在当前车站，那么根据这辆车的方向转移去下一个或上一个车站

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;int kase = 1, n, T, t[100], m1, m2, d[100], e[100];int t1[100][100], t2[100][100], dp[500][100];void solve() { for (int i = 1; i <= m1; i++) { t1[i][1] = d[i]; for (int j = 2; j <= n; j++) { t1[i][j] = t1[i][j-1] + t[j-1]; } } for (int i = 1; i <= m2; i++) { t2[i][n] = e[i]; for (int j = n-1; j >= 1; j--) { t2[i][j] = t2[i][j+1] + t[j]; } } memset(dp, INF, sizeof(dp)); dp[0][1] = 0; for (int i = 0; i <= T; i++) { for (int j = 1; j <= n; j++) { if (dp[i][j] == INF) continue; dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1); for (int k = 1; k <= m1; k++) { if (i == t1[k][j]) dp[i+t[j]][j+1] = min(dp[i+t[j]][j+1],dp[i][j]); } for (int k = 1; k <= m2; k++) { if (i == t2[k][j]) dp[i+t[j-1]][j-1] = min(dp[i+t[j-1]][j-1],dp[i][j]); } } }}int main() { //freopen("out.txt", "w", stdout); while (~scanf("%d", &n) && n) { scanf("%d", &T); for (int i = 1; i <= n-1; i++) scanf("%d", &t[i]); scanf("%d", &m1); for (int i = 1; i <= m1; i++) scanf("%d", &d[i]); scanf("%d", &m2); for (int i = 1; i <= m2; i++) scanf("%d", &e[i]); solve(); printf("Case Number %d: ", kase++); if (dp[T][n] == INF) printf("impossible\n"); else printf("%d\n", dp[T][n]); } return 0;}

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