Dowemo
0 0 0 0

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