Programozás‎ > ‎Feladatok‎ > ‎

Számháromszögek

Tekintsük az ábrán látható számháromszöget. 
          7

        3   8

      8   1   0

    2   7   4   4

  4   5   2   6   5

A felső csúcsból indulunk, mindig átlósan lefelé balra vagy jobbra léphetünk. Legfeljebb mennyi lehet az út során érintett számok összege? 

(A fenti ábrán a maximum 30: 7 -> 3 -> 8 -> 7 -> 5.)

Feladat

Írjunk programot, ami megadja a lehetséges legnagyobb összeget.

Bemenet

A bemenet első sora a háromszög sorainak R számát adja meg  (1 <= R <= 1000). Ezután a háromszög sorai következnek, mindegyikben szóközök választják el a számokat. Minden szám nemnegatív és legfeljebb 100.

Kimenet

A maximális összeg értéke.

Példa

Bemenet  Kimenet
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 
30


Tesztadatok

Címkék

A feladat forrása: USACO training material, Number Triangles
Algoritmusok: 

megoldás