POJ 1163 The Triangle 解题报告

一、问题描述

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

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Sample Output

30

 

二、解题思路

自上往下从每一层执行操作：对于第i层的第j个元素a[i][j]，首先读入a[i][j]，然后看a[i-1][j-1]和a[i-1][j]哪个大，把大的加到a[i][j]上。如果i==N是最后一层，还要维护一个最大值rowmax记录a[i][j]的最大值，最后输出rowmax。

由计算过程可知，计算第i层时只需要用到第i-1层的数据，因此可以用两个一维数组交替使用以节省空间。

 

三、代码

 

#include<iostream>
using namespace std;
int N;
int a[2][102];
int main()
{
    int i,j;
    cin>>N;
    int rowmax;
    for( i=1;i<=N;++i)
    {
        int row=(i%2);
        int other=(i+1)%2;
        rowmax=0;

        for(j=1;j<=i;++j)
        {
            cin>>a[row][j];
            if(a[other][j-1]>a[other][j])
                a[row][j]+=a[other][j-1];
            else
                a[row][j]+=a[other][j];
            if(i==N && rowmax<a[row][j])
                rowmax=a[row][j];
        }
    }
    cout<<rowmax<<endl;
    return 0;
}