AcWing 898. 数字三角形
原题链接
简单
作者:
AC_
,
2021-01-27 21:21:50
,
所有人可见
,
阅读 183
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 510;
int n;
int tri[MAX][MAX];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++)
cin >> tri[i][j];
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++) {
if (j == 1) tri[i][j] += tri[i - 1][j];
else if (j == i) tri[i][j] += tri[i - 1][j - 1];
else tri[i][j] += max(tri[i - 1][j - 1], tri[i - 1][j]);
}
int m = -11000;
for (int j = 1; j <= n; j ++)
if (tri[n][j] > m)
m = tri[n][j];
cout << m;
return 0;
}