网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[IOI1994]数塔
成绩 | 开启时间 | 2014年09月19日 星期五 10:04 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:04 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:04 |
输入文件 | shuta.in | 输出文件 | shuta.out |
数塔
问题描述
设有一个三角形的数塔,顶点结点称为根结点,每个结点有一个整数数值(小于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个整数,为所选路径,中间用一个空格隔开。
【输入样例】
输入文件名:shuta.in
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
【输出样例】
输出文件名:shuta.out
86
13 8 26 15 24