/*
Program računa maksimalnu sumu u zapisu brojeva u obliku trokuta. Problem se može riješiti
na nekoliko načina (npr. dinamičko programiranje), ovdje ćemo predstaviti rekurzivno rješenje.
Označimo s f(i,j) maksimalnu sumu koja završava na nekom putu odozdo prema gore na i-tom retku
i j-tom stupcu i neka je T 2D polje koje sprema unesene podatke i visine je h. || je mjera za duljinu.
Tada f(i,j) možemo rekonstruirati preko prijašnjih riješenja
T(i,j), i = h-1
f(i,j) ={
max{f(i+1,j), f(i+1,j+1) : j = 0,1, ..., |T(i+1)|-1}+T(i,j), 0<= i< h-1.
Kako svi putovi završavaju u početnom vrhu trokuta (0,0), onda i maksimalni put završava u (0,0)
*** komentar: koristimo memoizaciju kako bi spremeli vrijednosti prevog rekurzivnog računanja funkcije f
*/
#include <iostream>
using namespace std;
// C support
#include <cstdlib>
#include <cstring> // memset
// input from file
#include <fstream>
#define MEMO
#define NONE -1
#define MAX(a,b) ((a) > (b) ? (a) : (b))
int max_sum_trian(short T[100][100], int MaxSums[100][100], int row, int col, int height)
{
// varijable
int max_value;
// rekruzija
if (row == height-1) return T[row][col];
// rekurzivni poziv
#ifdef NO_MEMO
return (MAX(max_sum_trian(T,MaxSums, row+1, col,height), max_sum_trian(T,MaxSums, row+1, col+1,height))+T[row][col]);
#endif
// s memoizacijom
#ifdef MEMO
if (MaxSums[row+1][col] == NONE) MaxSums[row+1][col] = max_sum_trian(T,MaxSums, row+1, col,height);
if (MaxSums[row+1][col+1] == NONE) MaxSums[row+1][col+1] = max_sum_trian(T,MaxSums, row+1, col+1,height);
MaxSums[row][col] = MAX(MaxSums[row+1][col], MaxSums[row+1][col+1])+T[row][col];
return MaxSums[row][col];
#endif
}
int main()
{
// postavljanje podataka
// 2D apolje za spremanje podataka
short T[100][100];
int max_sums[100][100];
int n; // broj testnih primjera
int max_value; // rjesenje
int height; // visina trokuta
int num_of_Tests = 0;
cin >> n;
while(++num_of_Tests<=n)
{
// incijaliziraj polja T, max_sums
memset(T, 0, sizeof(T[0][0]) * 100 * 100);
memset(max_sums, NONE, sizeof(max_sums[0][0]) * 100 * 100);
// ucitavanje podataka trokuta
cin >> height;
int row = 0;
while(row < height)
{
for(int col = 0; col <= row; col++) cin >> T[row][col];
row++;
}
// rjesavanje problema
max_value = max_sum_trian(T,max_sums, 0,0, height);
// ispis outputa
cout << max_value << endl;
} // end of num_of_tests<n
}
LyoKICAgUHJvZ3JhbSByYcSNdW5hIG1ha3NpbWFsbnUgc3VtdSB1IHphcGlzdSBicm9qZXZhIHUgb2JsaWt1IHRyb2t1dGEuIFByb2JsZW0gc2UgbW/FvmUgcmlqZcWhaXRpCiAgIG5hIG5la29saWtvIG5hxI1pbmEgKG5wci4gZGluYW1pxI1rbyBwcm9ncmFtaXJhbmplKSwgb3ZkamUgxIdlbW8gcHJlZHN0YXZpdGkgcmVrdXJ6aXZubyByamXFoWVuamUuCiAgIAogICBPem5hxI1pbW8gcyBmKGksaikgbWFrc2ltYWxudSBzdW11IGtvamEgemF2csWhYXZhIG5hIG5la29tIHB1dHUgb2RvemRvIHByZW1hIGdvcmUgbmEgaS10b20gcmV0a3UKICAgaSBqLXRvbSBzdHVwY3UgaSBuZWthIGplIFQgMkQgcG9samUga29qZSBzcHJlbWEgdW5lc2VuZSBwb2RhdGtlIGkgdmlzaW5lIGplIGguIHx8IGplIG1qZXJhIHphIGR1bGppbnUuCiAgIFRhZGEgZihpLGopIG1vxb5lbW8gcmVrb25zdHJ1aXJhdGkgcHJla28gcHJpamHFoW5qaWggcmlqZcWhZW5qYSAKICAgCiAgIAkJCQkJICBUKGksaiksIGkgPSBoLTEKICAgCQkJZihpLGopID17IAogICAJCQkJCSAgbWF4e2YoaSsxLGopLCBmKGkrMSxqKzEpIDogaiA9IDAsMSwgLi4uLCB8VChpKzEpfC0xfStUKGksaiksIDA8PSBpPCBoLTEuCiAgIAkJCQogIEtha28gc3ZpIHB1dG92aSB6YXZyxaFhdmFqdSB1IHBvxI1ldG5vbSB2cmh1IHRyb2t1dGEgKDAsMCksIG9uZGEgaSBtYWtzaW1hbG5pIHB1dCB6YXZyxaFhdmEgdSAoMCwwKQogIAogICoqKiBrb21lbnRhcjoga29yaXN0aW1vIG1lbW9pemFjaWp1IGtha28gYmkgc3ByZW1lbGkgdnJpamVkbm9zdGkgcHJldm9nIHJla3Vyeml2bm9nIHJhxI11bmFuamEgZnVua2NpamUgZgoqLwoKCgojaW5jbHVkZSA8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBDIHN1cHBvcnQKI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxjc3RyaW5nPiAgLy8gbWVtc2V0CgovLyBpbnB1dCBmcm9tIGZpbGUKI2luY2x1ZGUgPGZzdHJlYW0+CgojZGVmaW5lIE1FTU8KI2RlZmluZSBOT05FICAgICAtMQoKI2RlZmluZSBNQVgoYSxiKSAoKGEpID4gKGIpID8gKGEpIDogKGIpKQoKCgppbnQgbWF4X3N1bV90cmlhbihzaG9ydCBUWzEwMF1bMTAwXSwgaW50IE1heFN1bXNbMTAwXVsxMDBdLCBpbnQgcm93LCBpbnQgY29sLCBpbnQgaGVpZ2h0KQp7CiAgLy8gdmFyaWphYmxlIAogIGludCBtYXhfdmFsdWU7CiAgLy8gcmVrcnV6aWphCiAgaWYgKHJvdyA9PSBoZWlnaHQtMSkgcmV0dXJuIFRbcm93XVtjb2xdOwogICAgCiAgLy8gcmVrdXJ6aXZuaSBwb3ppdgogICAgCiAgI2lmZGVmIE5PX01FTU8KICByZXR1cm4gKE1BWChtYXhfc3VtX3RyaWFuKFQsTWF4U3Vtcywgcm93KzEsIGNvbCxoZWlnaHQpLCBtYXhfc3VtX3RyaWFuKFQsTWF4U3Vtcywgcm93KzEsIGNvbCsxLGhlaWdodCkpK1Rbcm93XVtjb2xdKTsKICAjZW5kaWYKICAKICAvLyBzIG1lbW9pemFjaWpvbQogICNpZmRlZiBNRU1PIAogIGlmIChNYXhTdW1zW3JvdysxXVtjb2xdID09IE5PTkUpICAgTWF4U3Vtc1tyb3crMV1bY29sXSA9IG1heF9zdW1fdHJpYW4oVCxNYXhTdW1zLCByb3crMSwgY29sLGhlaWdodCk7CiAgaWYgKE1heFN1bXNbcm93KzFdW2NvbCsxXSA9PSBOT05FKSBNYXhTdW1zW3JvdysxXVtjb2wrMV0gPSBtYXhfc3VtX3RyaWFuKFQsTWF4U3Vtcywgcm93KzEsIGNvbCsxLGhlaWdodCk7CiAgCiAgTWF4U3Vtc1tyb3ddW2NvbF0gPSBNQVgoTWF4U3Vtc1tyb3crMV1bY29sXSwgTWF4U3Vtc1tyb3crMV1bY29sKzFdKStUW3Jvd11bY29sXTsKICByZXR1cm4gTWF4U3Vtc1tyb3ddW2NvbF07CiAgI2VuZGlmCiAgCiAgCn0KCgppbnQgbWFpbigpCnsKICAvLyBwb3N0YXZsamFuamUgcG9kYXRha2EKICAgLy8gMkQgYXBvbGplIHphIHNwcmVtYW5qZSBwb2RhdGFrYQogIAogIAogIHNob3J0IFRbMTAwXVsxMDBdOwogIGludCAgIG1heF9zdW1zWzEwMF1bMTAwXTsKICAKICBpbnQgICBuOyAvLyBicm9qIHRlc3RuaWggcHJpbWplcmEKICBpbnQgICBtYXhfdmFsdWU7IC8vIHJqZXNlbmplCiAgaW50ICAgaGVpZ2h0OyAgICAvLyB2aXNpbmEgdHJva3V0YQogIAogIGludCAgICAgIG51bV9vZl9UZXN0cyA9IDA7CiAgICAKICBjaW4gPj4gbjsgCiAgICAKICB3aGlsZSgrK251bV9vZl9UZXN0czw9bikKICB7CiAgICAKICAgIC8vIGluY2lqYWxpemlyYWogcG9samEgVCwgbWF4X3N1bXMKICAgIG1lbXNldChULCAwLCBzaXplb2YoVFswXVswXSkgKiAxMDAgKiAxMDApOwogICAgbWVtc2V0KG1heF9zdW1zLCBOT05FLCBzaXplb2YobWF4X3N1bXNbMF1bMF0pICogMTAwICogMTAwKTsKICAgIAogIAogICAgLy8gdWNpdGF2YW5qZSBwb2RhdGFrYSB0cm9rdXRhCiAgICBjaW4gPj4gaGVpZ2h0OwoKICAgIGludCByb3cgPSAwOwogICAgd2hpbGUocm93IDwgaGVpZ2h0KQogICAgewogICAgICBmb3IoaW50IGNvbCA9IDA7IGNvbCA8PSByb3c7IGNvbCsrKSBjaW4gPj4gVFtyb3ddW2NvbF07CiAgICAgIHJvdysrOwogICAgfQoKICAgIC8vIHJqZXNhdmFuamUgcHJvYmxlbWEKICAgIG1heF92YWx1ZSA9IG1heF9zdW1fdHJpYW4oVCxtYXhfc3VtcywgMCwwLCBoZWlnaHQpOwogICAgLy8gaXNwaXMgb3V0cHV0YQogICAgY291dCA8PCAgbWF4X3ZhbHVlIDw8IGVuZGw7CiAgICAKICB9IC8vIGVuZCBvZiBudW1fb2ZfdGVzdHM8bgogIAp9