Description

有一座五層的數字塔，第一層有 1 個數字，第二層有 2 個數字，以此類推
整座塔呈現三角形，每個數字只和下一個距離最近的兩個數字有樓梯連結
而且只能往下走，如下圖:

    1
   4 6
  6 9 3
 6 3 7 1
2 6 3 1 8

第二層的 4 只可以走到第三層的 6、9
第二層的 6 只可以走到第三層的 9、3

從第一層開始往下走
要如何從第一層走到最底層
使得經過的值加起來最大
將最大值輸出

註:
數字塔會包含 0
0 代表死路不能走
也就是路徑不能經過 0
但一定有至少一條路徑可以從第一層走到最底層

 

hint:

#include 

#define NINF -2147483648
#define SIZE 5

int max;

/* 傳入即將進入第幾層、第幾個位置以及目前為止的加總 */
void goThroughTower(int tower[SIZE][SIZE], int level, int index, int sum)
{
    if (level + 1 == SIZE) {
        /*
            ???
        */
    }
    else {
        /*
            ???
        */
    }
}

int main()
{
    int tower[SIZE][SIZE];
    int i, j;

    while (scanf("%d", &tower[0][0]) != EOF) {
        max = NINF;

        for (i = 1; i < SIZE; ++i) {
            for (j = 0; j <= i; ++j)
                scanf("%d", &tower[i][j]);
        }

        goThroughTower(tower, 0, 0, 0);

        printf("%d\n", max);
    }

    return 0;
}

Input

塔₁

...

塔_N

 

註: 塔內的數均為 1~2³¹-1 的正整數

N 為小於20的正整數

Output

最大值₁

...

最大值_N

 

註: 最後須加上換行

Sample Input  Download

Sample Output  Download

Tags

Discuss