Hust oj 1813 小乐乐要下山（dp + 路径还原）_综合

小乐乐要下山

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 292(123 users)

Total Accepted: 146(117 users)

Rating:

Special Judge: No

Description

 上学的路总是那么艰辛，在小乐乐辛苦的出了家门之后，她才想起自己的家已经搬到山上了（睡的真迷糊）。下山的路同样十分艰难，不同的地方通行的难易程度也不同。如图所示，小乐乐现在在山顶上，她面前有两条路，每条路通往一个地点，每个地点有一个值，表示这个通行的难易程度。最底层的地点就是山脚了。大家知道，小乐乐好懒好懒的，她想知道怎么下山最省力？

Input

 第一行一个整数n（1<n<500)
 随后n行，第i+1行有i个数字
 表示山上的路况

Output

 输出从山顶到山脚最省力的路。（保证答案唯一）

Sample Input

Sample Output

 1 2 5
 

Hint

 输入的是一个三角形，每个点能走到下面那个点和下右那个点。