1288 . D. [IOI 1994] 三角旅行
TopCoder
Tags
Description
7(圖一)
3 8
8 1 0
2 7 4 4
4 5 2 6 5
圖一是一個有數字構成的三角形. 現在請問 從最頂端走到最底端 最大的和是多少。
* 每個點只能往左下或右下走，底層的點不能再往下走。
* 三角形的高度介於1到100之間。
* 三角形上的數字都介於0到99之間。
Input Format
第一個是數字n代表三角形高度。
聰明的你知道接下來是怎樣的格式。
Output Format
輸出一個貌似解答的數字。
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
Hints
Problem Source
原TIOJ1288 / 雄中公假社'08 入退社考。(IOI 94 DayI pA)。Problem Setter：ggm。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |
Testdata and Limits
| No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
|---|---|---|---|---|
| 0 | 1000 | 65536 | 262144 | |
| 1 | 1000 | 65536 | 262144 | |
| 2 | 1000 | 65536 | 262144 | |
| 3 | 1000 | 65536 | 262144 | |
| 4 | 1000 | 65536 | 262144 | |
| 5 | 1000 | 65536 | 262144 |