| 题目名称 | 77. [IOI 1994]数字三角形 |
|---|---|
| 输入输出 | shuta.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 王国正
于2008-07-24加入修改该题
|
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：547， 提交：1223， 通过率：44.73% | ||||
|
谢兴宇 |
100 | 0.000 s | 0.00 MiB | Pascal |
|
皮波Forever |
100 | 0.000 s | 0.00 MiB | C++ |
|
王宸 |
100 | 0.000 s | 0.00 MiB | C++ |
|
汪泱泱 |
100 | 0.000 s | 0.00 MiB | C++ |
|
李宇航 |
100 | 0.000 s | 0.00 MiB | C++ |
|
老祖宗 |
100 | 0.000 s | 0.00 MiB | C++ |
|
_WA自动机 |
100 | 0.000 s | 0.00 MiB | C++ |
|
喃篱 |
100 | 0.000 s | 0.00 MiB | C++ |
|
邓世昌 |
100 | 0.000 s | 0.00 MiB | C++ |
|
黄笑凡 |
100 | 0.000 s | 0.00 MiB | C++ |
| 本题关联比赛 | |||
| 暑假培训七 | |||
| DP暑假B班欢乐水题赛 | |||
| 刷题ing | |||
| 关于 数字三角形 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
提交的时候吓死我了
| ||||
|
废了废了
ZZZ
2021-07-03 17:29
52楼
| ||||
|
递归输出路径
| ||||
|
不会
| ||||
|
不会
| ||||
|
不会
| ||||
|
不会
| ||||
|
不会
| ||||
|
不会
| ||||
|
不会
| ||||
【题目描述】
设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值（小于3000）。从顶点出发，可以向左走，也可以向右走。如图所示：从根结点13出发，向左走到达11，再向右走到达7，再向左走到达14，再向左走到达7.由于7是最底层，无路可走。此时，我们找到一条从根结点开始到达底层的路径：
13--11--7--14--7
路径上结点中数字的和称为路径的值，如上面路径的值为13+11+7+14+7=52。同时，从图中可以看到除了上述路径外，还存在其他的路径，如：
13--11--12--14--13
其路径的值为63。
问题：当三角形数塔给出后，找出一条路径，使路径上的值为最大。若这样的路径存在多条，选根部偏左的路径。
【输入格式】
输入由若干行组成，第一行有一个整数，n（1≤n≤80）；n表示数塔的层数。第2至n+1行是数塔的信息。
【输出格式】
输出由两行组成，第一行有一个整数，为所选路径的值。
第二行有n个整数，为所选路径，中间用一个空格隔开。
【输入样例】
5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11
【输出样例】
86 13 8 26 15 24