AcWing 898. 数字三角形
原题链接
简单
作者:
tyEyyu53
,
2024-04-10 19:48:24
,
所有人可见
,
阅读 1
#include<iostream>
using namespace std;
const int N =550 , INF = 1e9;
int a[N][N],f[N][N],n;
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
cin>>a[i][j];
for (int i=0;i<=n;i++)
for (int j=0;j<=i+1;j++)
f[i][j] = -INF;
f[1][1] = a[1][1];
for (int i=2;i<=n;i++)
for (int j=1;j<=i;j++)
f[i][j] = max(f[i-1][j] + a[i][j] , f[i-1][j-1] + a[i][j]);
int res = -INF;
for (int i=1;i<=n;i++) res = max(res , f[n][i]);
cout<<res;
}