The Triangle
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 47278 | Accepted: 28608 |
Description
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1)
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
573 88 1 0 2 7 4 44 5 2 6 5
Sample Output
30
//利用动态规划解决问题#includeusing namespace std;int a[101][101]; //二维数组储存三角形中的数int main(){ int n; cin>>n; for(int i=0;i >a[i][j]; for(int i=n-2;i>=0;i--) for(int j=0;j<=i;j++) a[i][j]+=(a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1]); //动态规划决策,从后往上加,加到最后最大值为顶端的值 cout< <