POJ 1163 The Triangle

简介: POJ 1163 The Triangle

The Triangle


Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)

Total Submission(s) : 23 Accepted Submission(s) : 18

Problem 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


从下往上推,相邻的两个数中找较大的与上层相加,得出的结果相邻的两个数中再找较大的与上层相加,以此类推。

#include<stdio.h>
int main()
{
    int n, i, j;
    scanf("%d", &n);
    int* *a = new int* [n];
    for(i = 0; i < n; ++i)
    {
        a[i] = new int[i + 1];
        for(j = 0; j <= i; ++j)
        {
            scanf("%d", &a[i][j]);
        }
    }
    for(i = n - 2; i >=0; --i)
    {
        for(j = 0; j <= i; ++j)
        {
            if(a[i+1][j]>a[i+1][j+1])
                a[i][j]+=a[i + 1][j];
            else
                a[i][j] +=a[i + 1][j + 1];
        }
    }
    printf("%d", a[0][0]);
    return 0;
}
目录
相关文章
|
机器学习/深度学习
poj 2155 Matrix (二维树状数组)
这是楼教主出的二维线段树或者是二维树状数组的题,题意很简单,就是有个n*n的矩阵,初始值都是0,然后给你两个操作,一个是给你左上角和右下角的坐标,把这个长方形的区间所有元素反取反(0变1 1变0),另一个是求某个具体坐标的值。 这里我用了二维的线树状数组,一维树状数组可以解决区间更新和点查询的问题,这里只需要加一维就可以了,代码比较好写,不过开始犯了很多低级的错误。
39 0
|
测试技术
POJ3687---Labeling Balls
POJ3687---Labeling Balls
POJ3687---Labeling Balls
HDU-1071,The area(求面积水题)
HDU-1071,The area(求面积水题)
Triangle Leetcode
Created by Wang, Jerry, last modified on Dec 20, 2015
Triangle Leetcode