A4397. 【动态规划】数塔
编程题
入门
知识点
题目描述
设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值（小于3000）。从顶点出发，可以向左走，也可以向右走。如图所示：从根结点13出发，向左走到达11，再向右走到达7，再向左走到达14，再向左走到达7.由于7是最底层，无路可走。此时，我们找到一条从根结点开始到达底层的路径：
13--11--7--14--7
路径上结点中数字的和称为路径的值，如上面路径的值为13+11+7+14+7=52。同时，从图中可以看到除了上述路径外，还存在其他的路径，如：
13--11--12--14
13--11--7--14--7
路径上结点中数字的和称为路径的值，如上面路径的值为13+11+7+14+7=52。同时，从图中可以看到除了上述路径外，还存在其他的路径，如：
13--11--12--14
输入格式
输入由若干行组成，第一行有一个整数，n（1≤n≤80）；n表示数塔的层数。第2至n+1行是数塔的信息。
输出格式
输出由两行组成。
第一行有一个整数n，为所选路径的值。
第二行有n个整数，为所选路径，中间用一个空格隔开。
第一行有一个整数n，为所选路径的值。
第二行有n个整数，为所选路径，中间用一个空格隔开。
输入输出样例
输入 #1
5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11
输出 #1
86 13 8 26 15 24