题目描述
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外,向左下走的次数与向右下走的次数相差不能超过 1。
输入输出样例
输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出
27
C++版代码如下(只通过了30%)文章来源:https://www.toymoban.com/news/detail-597936.html
#include <bits/stdc++.h>
using namespace std;
int a[1010][1010];
int main()
{
int r;
cin>>r;
for(int i=1;i<=r;i++)
{
for(int j=1;j<=i;j++)
cin>>a[i][j];
}
for(int i=2;i<=r;i++)
{
for(int j=1;j<=i;j++)
{
a[i][j]+=max(a[i-1][j],a[i-1][j-1]);//状态转移方程
}
}
int maxn=0;
for(int i=1;i<=r;i++)
if(a[r][i]>maxn)
maxn=a[r][i];
cout<<maxn;
return 0;
}
后续会出很多蓝桥杯题目解析和数据结构内容详解,欢迎关注
评论区可一起探讨学习文章来源地址https://www.toymoban.com/news/detail-597936.html
到了这里,关于【数字三角形】(C++版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!