学步园

/*

input:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

output:
30


    数字三角形，可以说是一道很经典的题了，这道题应该出现在dp的入门题里，
但是在这里提前介绍也是有原因的，因为递推中同样涉及了这个关系式的推导，
好了，来仔细研究下这个三角形吧，总之这个三角形很重要，思想和方法一定要
领会，在后面的很多题目中，都是这种类型题目的变形。

    要输出的是从三角形的顶部到最后一行的所有数字的和的问题，关于这个问题
我想在小学奥数中肯定接触过诸如此类类似的题目，当时大家是怎么解决?QAQ,忘了
忘了，肯定是草稿上乱撸一片，然后就出来了一个看似正确的结果，再将其放进去了
  TAT，这样的学习是错误的，学习就应该抓本质和抓概念，而不能抓作业和抓考试，
否则到头来，啥东西也没学会。。。。。

先看看这个题吧，我们采用倒推的手段来处理这个题目，首先，我们假设a[i][j]中
存放的是我们需要的数值，也就是说，a[i][j]表示的是从第一行到第i行的最优的
那条路线和，但是，我们却要用a[i+1][j+1]来表示题目中的的最后一行。
然后由a[i][j]+=max{a[i+1][j],a[i+1][j+1]}从结果行到第一行一次递归运算就行了，
最后输出a[1][1]就是我们需要的结果了。因为，a[i][j]存放的是才第i行到i+1行的
最优路线和，而a[i-1][j-1]存放的确实第i-1行到第i+1行的最优路线和，一次一次的
往前推，认真想，肯定是能想会的，那么a[1][1]就是我们需要的最优路线和了。







*/



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

using namespace std;

int a[123][123];

int main(void)
{
    memset(a,0,sizeof(a));
    int n;cin>>n;
    for ( int i = 1;i <= n;i++ )
        {
            for ( int j = 1;j <= i;j++ )
                {
                    cin>>a[i][j];
                }
        }

        for ( int i = n-1;i >= 1;i-- )
            {
                for ( int j = 1;j <= i;j++ )
                    {
                        if ( a[i+1][j] > a[i+1][j+1] )
                                a[i][j]+=a[i+1][j];
                            else
                                a[i][j]+=a[i+1][j+1];
                    }
            }
            cout<<a[1][1]<<endl;


    return 0;
}

实验室这几天没流量了，不知道是哪个片帝在用P2P下片，导致我写了好多东西都没办法上传，也刷不了题了QAQ，，，，