You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

33 lines
743 B

#include <bits/stdc++.h>
using namespace std;
int a[101][101] = {0};
int f[101][101] = {0};
int main() {
//输入+输出重定向
freopen("../1272.txt", "r", stdin);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; ++j) {
cin >> a[i][j];
}
}
//初始化最后一行的dp
for (int i = 1; i <= n; ++i) {
f[n][i] = a[n][i];
}
//从倒数第二行开始,反向建构
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; ++j) {
f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1]);
}
}
cout << f[1][1] << endl;
//关闭文件
fclose(stdin);
return 0;
}