suma_max_triunghi_dynamic

#include    <iostream>
#include    <fstream>

using namespace std;

ifstream f("triunghi.in");
int n, a[20][20], p[20][20], S[20][20];

void input(){
    f >> n;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j) f >> a[i][j];
    f.close();
}

void init(){
    for(int i = 1; i <= n; ++i) S[n][i] = a[n][i];
}

void dynamic(){
    for(int i = n-1; i >= 1; --i)
    for(int j = 1; j <= i; ++j)
    if(S[i+1][j] > S[i+1][j+1]){
        S[i][j] = a[i][j] + S[i+1][j];
        p[i][j] = 1;
    }
    else{
        S[i][j] = a[i][j] + S[i+1][j+1];
        p[i][j] = 2;
    }
}

void print(){
    int q = 1, r = 1;
    for(int i = 1, j = 1; i < n; ++i){
        if(p[i][j] == 2){
            r++;
            j++;
        }
        q++;
        cout << a[q][r] << "+";
    }
    cout << '\b' << " " << "\n";
}

int main()
{
    input();
    init();
    dynamic();
    print();
    return 0;
}