1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
int N,i,j;
int Map[110][110],Opt[110][110];
int main(){
    scanf("%d\n",&N);
    for (i=1;i<=N;i++)
      for (j=1;j<=i;j++) scanf("%d",&Map[i][j]);
    memset(Opt,0,sizeof(Opt));
    Opt[1][1]=Map[1][1];
    for (i=2;i<=N;i++)
      for (j=1;j<=i;j++){
          if (j==1) Opt[i][j]=Opt[i-1][j]+Map[i][j];else
          if (j==i) Opt[i][j]=Opt[i-1][j-1]+Map[i][j];else
          Opt[i][j]=max(Opt[i-1][j-1],Opt[i-1][j])+Map[i][j];
      }
    int Max=0;
    for (i=1;i<=N;i++) Max=max(Opt[N][i],Max);
    printf("%d\n",Max);
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX