AcWing 898. 数字三角形
原题链接
简单
作者:
next
,
2021-02-04 21:17:59
,
所有人可见
,
阅读 298
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int a[N][N],f[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
if(j>1&&j!=i)
f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
else
if(j==1)
f[i][j]=f[i-1][j]+a[i][j];
else f[i][j]=f[i-1][j-1]+a[i][j];//需要处理每行两端的数字可能遇到从负数和必定的0之间取0造成的错误。此时特判并累加负数到决策结果上
}
int res=0;
for(int i=1;i<=n;i++)res=max(res,f[n][i]);
cout<<res<<endl;
return 0;
}