1262:【例9.6】挖地雷
# 题目描述
在一个地图上有n个地窖(
# 输入
第一行:地窖的个数;
第二行为依次每个地窖地雷的个数;
下面若干行:
最后一行为"0 0"表示结束。
# 输出
挖到最多的雷。
# 样例
# 输入样例
6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 输出样例
3-4-5-6
34
1
2
3
2
3
# 源代码
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 205;
int a[N][N], c[N], f[N];
int main() {
int n, x, y, t, r, maxx = 0;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i][i];
while (cin >> x >> y) {
if (!x && !y) break;
a[x][y] = 1;
}
for (int i = 1; i <= n; i++) {
f[i] = a[i][i];
for (int j = 1; j < i; j++) {
if (a[j][i] && f[j] + a[i][i] > f[i]) {
f[i] = f[j] + a[i][i];
c[i] = j; //表示最好从j处挖到i处
}
}
if (f[i] > maxx) {
maxx = f[i];
t = i;
}
}
while (c[t]) {
r = c[t];
c[t] = -1;
t = r;
}
cout << t;
while (++t <= n) {
if (c[t] < 0) printf("-%d", t);
}
printf("\n%d", maxx);
return 0;
}
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
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
上次更新: 2022/03/08, 01:01:22