dp
dp[T] [N]表示在时间 i 时已经在第 j 个车站了，还需要等的时间。
由于dp[i] [j]只会与时间大于 i 的结果有关，所以 i 从后往前更新。
在T时间，如果在N站，则需要等的时间为0；如果不在N站，则永远不能到达，设置时间为INF，以便判断答案是否为“impossible”。
在更新之前，dp[i] [j] = dp[i+1] [j] + 1.这是最基础的，因为dp[i+1]已经全部更新完，所以dp[i] 可以在dp[i+1]的基础上更新。如果在 i 时刻没有方法减少等待时间的话，则只能等1s，以到达 i+1，则若无更好的方法，i 时刻等待时间绝不会少于dp[i+1] [j] + 1，且 i 时刻的等待时间也绝不会多于dp[i+1] [j] + 1，所以把dp[i] [j]先设置为 dp[i+1] [j] + 1 是正确的。
由于只有当 i 时刻 j 站有车发车时才会有优化的可能性，所以要预处理出每个时间点，每一站是否有发车。
接着就是 i 基于 i+1 更新，j 随便从哪个方向更新，因为 j 可能受到 j-1 方向的影响，也可能受到 j+1 方向的影响，两者无优先关系。我是从后往前更新 j ，但从前往后也是正确的。
注意更新dp时，时间不能超过T，因为如果超过T，而你还在车上，则答案应该为INF，或者说没有意义了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
int N, T, M1, M2, tt;
int t[100], m1[100], m2[100], dp[500][100], has_train[2][500][100];
int main() {
while (1) {
tt++;
scanf("%d", &N);
if (!N)break;
memset(dp, 0x3f, sizeof(dp));
memset(has_train, 0, sizeof(has_train));
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", &m1[i]);
scanf("%d", &M2);
for (int i = 1; i <= M2; i++)scanf("%d", &m2[i]);
for (int i = 1; i <= M1; i++) {
int cnt = 1, tnt = m1[i];
while (tnt <= T && cnt <= N) {
has_train[0][tnt][cnt] = 1;
if (cnt == N)break;
tnt += t[cnt];
cnt++;
}
}
for (int i = 1; i <= M2; i++) {
int cnt = N, tnt = m2[i];
while (tnt <= T && cnt >= 1) {
has_train[1][tnt][cnt] = 1;
if (cnt == 1)break;
tnt += t[cnt - 1];
cnt--;
}
}
dp[T][N] = 0;
for (int i = T - 1; i >= 0; i--) {
for (int j = N; j >= 1; j--) {
dp[i][j] = dp[i + 1][j] + 1;
if (j < N&&has_train[0][i][j] && i + t[j] <= T) {
dp[i][j] = min(dp[i][j], dp[i + t[j]][j + 1]);
}
if (j > 1 && has_train[1][i][j] && i + t[j - 1] <= T) {
dp[i][j] = min(dp[i][j], dp[i + t[j - 1]][j - 1]);
}
}
}
printf("Case Number %d: ", tt);
if (dp[0][1] >= INF)printf("impossible\n");
else printf("%d\n", dp[0][1]);
}
return 0;
}
|
