AcWing 898. 数字三角形
原题链接
简单
作者:
算法-小废物
,
2023-03-28 12:00:39
,
所有人可见
,
阅读 127
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n;
int f[N][N],a[N][N]; // f[i][j]表示从第i行第j个位置出发到底部的最大路径和,a[i][j]表示第i行第j个位置的数字
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
cin>>a[i][j];
}
// 初始化最后一行的f值,即为a数组最后一行的值
for(int i=1;i<=n;i++)
f[n][i]=a[n][i];
// 从倒数第二行开始计算f值
for(int i=n-1;i>0;i--)
for(int j=1;j<=i;j++)
{
// 当前位置的f值为下一行相邻两个位置f值的最大值加上当前位置的数字
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
}
cout<<f[1][1]<<endl; // 输出最大路径和
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~