1625 數字金字塔

1625 數字金字塔

鏈接：http://codevs.cn/problem/1625/

?

USACO

?時間限制: 1 s

?空間限制: 128000 KB

?

題目描述?Description

考慮在下面被顯示的數字金字塔.

寫一個程序來計算從最高點開始在底部任意處結束的路徑經過數字的和的最大.

每一步可以走到下方的點也可以到達右下方的點.

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

?在上面的樣例中,從 7 到 3 到 8 到 7 到 5 的路徑產生了最大和:30

輸入描述?Input Description

第一個行包含 R(1<= R<=1000) ,表示行的數目.

后面每行為這個數字金字塔特定行包含的整數.

所有的被供應的整數是非負的且不大于 100

輸出描述?Output Description

單獨的一行包含那個可能得到的最大的和.

樣例輸入?Sample Input

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

樣例輸出?Sample Output

30

數據范圍及提示?Data Size & Hint

題解：h[i][j]存該點數值， f[i][j]存從底部到該點的最大和，為該點值+Max（該點正下方最大和，該點斜下方最大和），即

f[i][j]=max(f[i+1][j]+h[i][j],f[i+1][j+1]+h[i][j]);

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int h[1005][1005],f[1005][1005];
int main(){int n;cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)scanf("%d",&h[i][j]);for(int j=1;j<=n;j++)f[n][j]=h[n][j];int i=n;while(i>1){i--;for(int j=1;j<=i;j++)f[i][j]=max(f[i+1][j]+h[i][j],f[i+1][j+1]+h[i][j]);}cout<<f[1][1]<<endl;
}

?