题目
题目描述
某城市地铁是线性的,有\(n\)（\(2\leq n\leq50\)）个车站,从左到右编号\(1\sim n\)。有\(M_1\)辆列车从第\(1\)站开始往右开,还有\(M_2\)辆列车从第\(n\)站开始往左开。列车在相邻站台间所需的运行时间是固定的，因为所有列车的运行速度是相同的。在时刻\(0\)，Mario从第\(1\)站出发,目的在时刻\(T\)（\(0leq
Tleq200\)）会见车站\(n\)的一个间谍。在车站等车时容易被抓，所以她决定尽量躲在开动的火车上,让在车站等待的时间尽量短。列车靠站停车时间忽略不计,且Mario身手敏捷,即时两辆方向不同的列车在同一时间靠站,Mario也能完成换乘。
输入输出格式
输入格式
输入文件包含数种情况，每一种情况包含以下7行：
第一行是一个正整数\(n\)，表示有\(n\)个车站 第二行是为\(T\)，表示Mario在时刻\(T\)见车站\(n\)的间谍 第三行有\(n-1\)个整数\(t_1\)，\(t_2\),...,\(t_{n-1}\),其中\(t_i\)表示地铁从车站\(i\)到\(i+1\)的行驶时间 第四行为\(M_1\)，及从第一站出发向右开的列车数目
第五行包含\(M_1\)个正整数\(a_1\),\(a_2\),...,\(a_{M_1}\)，即个列车出发的时间 第六行为\(M_2\)，及从第一站出发向右开的列车数目
第七行包含\(M_2\)个正整数\(b_1\),\(b_2\),...,\(b_{M_2}\)，即个列车出发的时间
最后一种情况以一行0结尾。
输出格式
有若干行，每行先输出Case Number XXX:（XXX为情况编号，从\(1\)开始），再输出最少等待时间或impossible（无解）。
输入输出样例
输入样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 4
55
5 10 15
4
0 5 10 20
4
0 5 10 15
4
18
1 2 3
5
0 3 6 10 12
6
0 3 5 7 12 15
2
30
20
1
20
7
1 3 5 7 11 13 17
0
|
输出样例
1
2
3
| Case Number 1: 5
Case Number 2: 0
Case Number 3: impossible
|
题解
紫书经典DP, 比较基础就不说了
代码
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
| #include <iostream>
#include <cstring>
#include <algorithm>
const int kInfinity(0x3f3f3f3f);
int n, T, M1, M2, kase;
int t[55];
bool trainl[55][10010];
bool trainr[55][10010];
int dp[10010][55];
int main(){
while (std::cin >> n && n) {
kase++;
std::cin >> T;
memset(t, 0, sizeof(t));
memset(trainl, 0, sizeof(trainl));
memset(trainr, 0, sizeof(trainr));
for (register int i(1); i < n; ++i) std::cin >> t[i];
std::cin >> M1;
for (register int i(1); i <= M1; ++i) {
register int t1;
std::cin >> t1;
register int sum(t1);
for (register int j(1); j <= n; ++j) {
trainl[j][sum] = 1;
sum += t[j];
}
}
std::cin >> M2;
for (register int i(1); i <= M2; ++i) {
register int t2;
std::cin >> t2;
register int sum(t2);
for (register int j(n); j >= 1; --j) {
trainr[j][sum] = 1;
sum += t[j - 1];
}
}
for (register int i(1); i < n; ++i)
dp[T][i] = kInfinity;
dp[T][n] = 0;
for (register int i(T-1); i >= 0; --i)
for (register int j(1); j <= n; ++j) {
dp[i][j] = dp[i + 1][j] + 1;
if (j < n && trainl[j][i] && i + t[j] <= T)
dp[i][j] = std::min(dp[i][j], dp[i + t[j]][j + 1]);
if (j > 1 && trainr[j][i] && i + t[j - 1] <= T)
dp[i][j] = std::min(dp[i][j], dp[i + t[j - 1]][j - 1]);
}
std::cout << "Case Number " << kase << ": ";
if (dp[0][1] >= kInfinity) std::cout << "impossible\n";
else std::cout << dp[0][1] << "\n";
}
return 0;
}
|