关于The Triangle的题解

时间：2014-03-29 23:05:57 收藏：0 阅读：677

作为一个ACM新手中的新手，这个代码是借鉴了网上许多大神写的......所以请勿嘲讽- -

Description

7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

(Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

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

Sample Output

30

题目的大概意思是输入一个三角数组，每个数字可以与下面一行相邻两个数字中一个相加，求出和的最大值。

代码如下

#include<iostream>

using namespace std;

int main()
{
    int n,i,j,a[100][100];
    while(cin >> n)
    {
        for(i=0;i<n;i++)
            for(j=0;j<=i;j++)
                cin >> a[i][j];
        for(i=n-2;i>=0;i--)
            for(j=i;j>=0;j--)
                a[i][j]+=a[i+1][j] > a[i+1][j+1] ? a[i+1][j] : a[i+1][j+1];     //从第n-1行开始往上，将每行每个元素与下面一行相邻两个数分别求和进行比较的出最大
        cout << a[0][0] << endl;
    }
}

关于The Triangle的题解,布布扣,bubuko.com

原文：http://www.cnblogs.com/futurehacker/p/3632884.html