文件名称：A Spy in the Metro UVA – 1025 dp
文件大小：32KB
文件格式：PDF
更新时间：2024-01-27 03:38:29
dp IN metro
题目链接：https://vjudge.net/problem/UVA-1025 紫书P268 书上是按照T从大到小 题意：第一行输入n，为n个车站，第2行为T，第三行表示从i到i+1车站所需时间，下面两行表示从1号车站向右走到n号车站有多少班车以及出发时间，最后两行表示从n号到1号的车出发时间，求在时间T到达n号车站在车站等待的最少时间。 思路：dp【i】【j】表示在第i分钟j号车站已经等待的时间。has_train【i】【j】【k】表示第i分钟车站j是否有车。k=0表示从左向右，k=1从右向左。当前状态有三种抉择：1.等待一分钟 2.坐车向左 3.坐车向右 错误的dp方程