ピラミッド C++編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
三角形状に並んだ N 段のピラミッドがあります。
上から i 段目には i 個のマスがあります。
各マスには整数値が書かれています。
あなたは最上段のマスから出発し、次のどちらかへ移動できます。
左下の隣のマス
右下の隣のマス
通ったマスの値の合計をスコアとします。
最下段まで到達できる経路のうち、スコアの最大値を出力してください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N
a_11
a_21 a_22
...
a_N1 a_N2 ... a_NN
1 行目にピラミッドの段数 N が入力されます。
続く N 行に、各段のマスの値が左から順に空白区切りで入力されます。
上から i 段目には i 個の整数が入力されます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
最上段から最下段まで移動する経路のうち、通ったマスの値の合計の最大値を 1 行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 1000
・ 0 ≦ a_ij ≦ 100
- 入力例1
-
4
3
7 4
2 4 6
8 5 9 3
- 出力例1
-
23
- 入力例2
-
7
7
11 11
3 11 8
4 0 4 15
7 7 7 14 4
2 3 13 7 14 12
4 10 9 10 8 10 14
- 出力例2
-
79
