Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Adapted from USACO by Ibrahim Mesecan.
Minimum Sum Triangle - DP
Consider the number triangle shown on the right.
Write a program that
calculates the smallest sum of numbers that can be passed on a
route that starts at the top and ends somewhere on the base.
Similar to Pascal Triangle, each step can go either diagonally
down to the left or diagonally down to the right.
Question:
Write a program that finds the smallest sum that starts at the
top and ends somewhere at the base.
Input specification
The first line contains an integer (n) which represents
the number of rows. Then, in the following n lines,
you will be given numbers which are between 0 and 1000.
The numbers are given such that
- the first line will have one number
- the second line will have two numbers
: : : - the nth line will have n numbers
where 1 ≤ n ≤ 250.
Output specification
A single line containing the smallest sum using
the traversal specified.
Sample Input I
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
|
Sample Output I
17
|
Для отправки решений необходимо выполнить вход.
|