代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], f[N][N];
int n;
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i; j ++)
cin >> g[i][j];
// 初始化,当对于边界之外的点置为负无穷,那么因为下面的 max 函数,就不会访问边界之外的点了
memset(f, -0x3f, sizeof f);
int res = -INF;
f[1][1] = g[1][1];
// 下面会用到 i-1 为了防止数组越界,我们让 i 从 1 开始存储
for(int i = 2; i <= n; i ++)
for(int j = 1; j <= i; j ++)
f[i][j] = max(f[i - 1][j - 1] + g[i][j], f[i - 1][j] + g[i][j]);
for(int j = 1; j <= n; j ++)
res = max(res, f[n][j]);
cout << res << endl;
return 0;
}