题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

注意事项

1. 三角形中可以有负值，因此$mx$要初始化为$-0x3f$。
2. f数组一定要$memset$，防止更新错误。
3. 可以在一开始就把$f$数组赋为$a$数组对应的值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int f[N][N],n,a[N][N],mx=-0x3f; 
int main()
{
    memset(f,-0x3f,sizeof(f)); 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            scanf("%d",&a[i][j]),f[i][j]=a[i][j];
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            if(j>1) f[i][j]+=max(f[i-1][j],f[i-1][j-1]);
            else f[i][j]+=f[i-1][j];
    for(int i=1;i<=n;i++) mx=max(mx,f[n][i]);
    printf("%d",mx); 
    return 0;
}