用DP求解。如果用搜索或是枚举，由于题目数据有R = 1000,用深搜，枚举量很大。用贪心会导致错误解，可以模拟贪心对下面的图算一下，是29。用DP，自顶向下，对每个数，求出顶点到它的最大和，这样保证了正确性，效率高。
        
               / max(F[k -1, i - 1], F[k - 1, i])   (k > 0)
F(k, i) =
               \ F[0, 0]   (k = 0)
                                    7
                                   F:7
                               3        8
                              F:10    F:15
                          8         1         0
                         F:18    F:16    F:15
                   2          7         4           4 
                F:20     F:25     F:23       F:19
           4           5           2         6           5
       F:24       F:30       F:27    F:29       F:24



/**//*
PROG: numtri
LANG: C
*/
#include<stdio.h>
#define max 1000
#define Max(a, b)( a > b ? a : b)
int s[max][max], F[max][max];
int main()
{
    FILE * fin = fopen("numtri.in", "r");
    FILE * fout = fopen("numtri.out", "w");
    int i, j, n;
    fscanf(fin, "%d", &n);
    for (i = 0; i < n; i++)
    {
        for (j = 0; j <= i; j++)
        {
            fscanf(fin, "%d", &s[i][j]); 
            F[i][j] = MAX(i, j);//保存从顶点s[0][0]到s[i][j]的最大和F[i][j]。
        }
    }
    n = 0;
    for (j = 0; j < i; j++)
    {
        n = Max(F[i - 1][j], n);
    }
    fprintf(fout, "%d\n", n);
    return 0; 
}
int MAX(int i, int j)
{
    if (i == 0)
    {
        return s[i][j];
    }
    else
    {
        if (j == 0)
        {
            return s[i][j] + F[i - 1][j];
        }
        else if (j == i)
        {
            return s[i][j] + F[i - 1][j - 1];
        }
        else
        {
            return Max(F[i - 1][j - 1], F[i - 1][j]) + s[i][j];
        }
    }
}