数塔

C ++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 50;

int a[N][N][4];
int n;

void number_tower(int n){
    //a[i][j][1]保存数塔值,a[i][j][2]记录最大路径值,a[i][j][3]记录路径
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= i; j ++){
            scanf("%d", &a[i][j][1]);//读入塔值
            a[i][j][2] = a[i][j][1];//最初路径最大值为其本身
            a[i][j][3] = 0;//路径初始化
        }
    }

    //计算数塔最大值并记录最大路径
    for(int i = n - 1; i >= 1; i --){
        for(int j = 1; j <= i; j ++){
            if(a[i + 1][j][2] > a[i + 1][j + 1][2]){
                a[i][j][2] = a[i][j][2] + a[i + 1][j][2];
                a[i][j][3] = 0;//从左下方上来
            }
            else{
                a[i][j][2] = a[i][j][2] + a[i + 1][j + 1][2];
                a[i][j][3] = 1;//从右下上来
            }
        }
    }

    //输出最大路径值
    printf("max = %d\n", a[1][1][2]);

    //输出最大路径
    int j = 1;
    for(int i = 1; i <= n - 1; i ++){
        printf("%d -> ", a[i][j][1]);
        j = j + a[i][j][3];
    }
    printf("%d\n", a[n][j][1]);
}

int main(){
    printf("please input the number of rows:\n");
    scanf("%d", &n);
    number_tower(n);
    return 0;
}

输入：

5
9 12 15 10 6 8 2 18 9 5 19 7 10 4 16

输出

please input the number of rows:
max = 59
9 -> 12 -> 10 -> 18 -> 10