2584 問題 O: 藍(lán)橋杯2020年第十一屆省賽真題-數(shù)字三角形
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 2043 解決: 653
題目描述
上圖給出了一個(gè)數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對(duì)于每條路徑，把路徑上面的數(shù)加起來可以得到一個(gè)和，你的任務(wù)就是找到最大的和。
路徑上的每一步只能從一個(gè)數(shù)走到下一層和它最近的左邊的那個(gè)數(shù)或者右邊的那個(gè)數(shù)。此外，向左下走的次數(shù)與向右下走的次數(shù)相差不能超過 1。
輸入
輸入的第一行包含一個(gè)整數(shù)N(1<N≤100)，表示三角形的行數(shù)。下面的 N行給出數(shù)字三角形。數(shù)字三角形上的數(shù)都是 0至 100之間的整數(shù)。
輸出
輸出一個(gè)整數(shù)，表示答案。
樣例輸入
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
樣例輸出
27
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情
比賽公告
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111