题目描述
输入一个n(1 <= n<= 350)层的三角形,像这样:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
第i层有i个数(每个数不超过100),编写一个程序,找到从第1层到第n层的所有路线中,权值之和最大的路线,并输出该路线的权值和。规定:第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。
输入描述
第一行输入一个整数n,表示三角形的层数。
第二行到第n+1行:第i + 1行包含i个以空格分隔的整数,表示三角形的第i行。
输出描述
输出一行,包含一个整数,表示最长上升子序列的长度。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
提示
中的权值和最大的路线:
7
*
3 8
*
8 1 0
*
2 7 4 4
*
4 5 2 6 5