AcWing 898. 数字三角形
原题链接
简单
作者:
tksj
,
2024-05-19 09:40:05
,
所有人可见
,
阅读 1
// f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + v[i][j]
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int f[N][N], v[N][N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
cin >> v[i][j];
}
}
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
f[i][j] = -1e9;
}
}
f[1][1] = v[1][1];
for (int i = 2; i <= n; ++i) {
for (int j = 1; j<= i; ++j) {
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + v[i][j];
}
}
int res = -1e9;
for (int i = 1; i <= n; ++i) {
res = max(res, f[n][i]);
}
cout << res << endl;
}