/*
三角形最大和问题
Time Limit:1000MS  Memory Limit:65536K
Total Submit:79 Accepted:22
Description
现在经常有一些数学问题困扰着小明。有如下一个三角形，
    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5
小明想求出从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。现在想请你编一个程序实现这个问题。
说明：
（1）每一步可沿左斜线向下或右斜线向下；
（2）1＜三角形行数≤100;
（3）三角形中的数字为0,1,...,99。
Input
输入有多个实例。每个测试用例的第一行是三角形的行数n，接下来是n行数字，每行数字的个数由1开始，依次加1。
Output
输出每个测试用例的最大和（整数），每行1个。
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
Source
*/
#include<stdio.h>
int s[100][100]={0};
int fun(int x,int y,int a,int b)
{
    if(s[x][y]==-1)
    {
       b=a&gt;b?a:b;
       return b;
    }
    a=s[x][y]+a;
    b=fun(x+1,y,a,b); //左下
    b=fun(x+1,y+1,a,b); //右下
    b=a&gt;b?a:b;
    return b;
}
main()
{
     int n,i,j;
     scanf("%d",&n);
     for(i=0;i&lt;n;i++)
     {
        for(j=0;j&lt;i+1;j++)
        {
            scanf("%d",&s[i][j]);
        }
      fflush(stdin);
      s[i][j]=-1;
     }
     for(int x=0;x&lt;j+1;x++)
     s[i][x]=-1;
     printf("%d",fun(0,0,0,0));
}