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
27
28
29
30
31
#include<iostream>
#include<cstring>
using namespace std;
int a[205][205],dp[205][205];
int max(int a,int b)
{
    int temp;
    temp=a>b?a:b;
    return temp;
}
int main()
{
    int n,i,j,nmax;
    cin>>n;
    memset(a,0,sizeof(a));
    for (i=1;i<=n;i++)
        for (j=1;j<=i;j++)
        cin>>a[i][j];
    nmax=0;
    memset(dp,0,sizeof(dp));
    for (i=1;i<=n;i++)
        for (j=1;j<=i;j++)
         dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
    for (i=1;i<=n;i++)
        if (dp[n][i]>nmax) {
                nmax=dp[n][i];
        }
    cout<<nmax<<endl;
    return 0;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX