Dowemo

problem 1002 number tower Baseline time limit: 1 seconds space limit: 131072 kb score: 5 difficulty: algorithm Collect Focus on a triangle consisting of a highly n positive integer, from above to below, to get the number and the maximum value. It can only lead to the next level of adjacent numbers, for example, from 6 of layer 3, which can only lead to 2 or 9 on the layer 4 layer.
5 8 4 3 6 9 7 2 9 5
The best scenario in the example is: 5 + 8 + 6 + 9 = 28 input

第1行:N,N为数塔的高度。(2 <= N <= 500)


第2 - N + 1行:每行包括1层数塔的数字,第2行1个数,第3行2个数......第k+1行k个数。数与数之间用空格分隔(0 <= A[i] <= 10^5) 。





Output

输出最大值





Input example

4


5


8 4


3 6 9


7 2 9 5





Output example

28







chinese

Idea: simple dynamic programming from top to bottom, finally output the value of the top a [ 1 ] [ 1 ]


#include<iostream>


using namespace std;


__int64 a[505][505];


int main()


{


 int n;


 cin>>n;


 for(int i=0; i<n; i++)


 for(int j=0; j<=i; j++)


 cin>>a[i][j];


 for(int i=n-2; i>=0; i--)


 for(int j=0; j<=i; j++)


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


 cout<<a[0][0]<<endl;


 return 0;


}












Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs