題目 2584:
藍橋杯2020年第十一屆省賽真題-數(shù)字三角形
時間限制: 2s
內存限制: 192MB 提交: 2043 解決: 653
題目描述
上圖給出了一個數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數(shù)加起來可以得到一個和，你的任務就是找到最大的和。
路徑上的每一步只能從一個數(shù)走到下一層和它最近的左邊的那個數(shù)或者右邊的那個數(shù)。此外，向左下走的次數(shù)與向右下走的次數(shù)相差不能超過 1。
輸入格式
輸入的第一行包含一個整數(shù)N(1<N≤100)，表示三角形的行數(shù)。下面的 N行給出數(shù)字三角形。數(shù)字三角形上的數(shù)都是 0至 100之間的整數(shù)。
輸出格式
輸出一個整數(shù)，表示答案。
樣例輸入
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
樣例輸出
27