【数字三角形】(C++版)

这篇具有很好参考价值的文章主要介绍了【数字三角形】(C++版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述
数字三角形c++编程,c++,算法,图论

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外,向左下走的次数与向右下走的次数相差不能超过 1。

输入输出样例
输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出

27

C++版代码如下(只通过了30%)

#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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数字三角形】

    题目描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外,向左下走

    2024年02月05日
    浏览(51)
  • 【洛谷】数字三角形(动态规划)

    目录 边读边存 优化成一维数组——倒序没用了? 从上往下存,最大值存在最后一行,最后遍历最后一行得到最大值的写法  边读边存,可以有效降低时间复杂度 在上一篇文章(【洛谷】采药(01背包问题))将二维数组优化成一维数组的过程中,内层循环我们是采用倒序的方

    2024年02月16日
    浏览(38)
  • 【题解 | 基础动态规划】:数字三角形

    链接: [USACO1.5] [IOI1994]数字三角形 Number Triangles 观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 在上面的样例中,从 7 → 3 → 8 → 7 → 5 7 to 3 to 8 to 7 to 5 7 →

    2024年04月14日
    浏览(50)
  • 动态规划入门(数字三角形模型)

    备战 2024年蓝桥杯算法学习 -- 每日一题 Python大学A组         试题一:摘花生         试题二:最低通行费用         试题三:方格取数         试题四:传纸条 【题目描述】         Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩

    2024年04月14日
    浏览(40)
  • AcWing 898. 数字三角形 (每日一题)

    像数组下标 出现 i-1 的,在循环的时候从 i=1 开始。 0x3f3f3f3f : 1061109567 Integer.MAX_VALUE : 2147483647 在选用 Integer.MAX_VALUE 时,很可能会出现 数据溢出 。 所以在用 Integer.MAX_VALUE 时 需要先取 MAX 再加 a[i][j]; 注:做 数字三角形 这题时, 初始化时需要注意一下边界 。 由于我们 状态计

    2024年02月11日
    浏览(39)
  • 数字三角形+包子凑数(蓝桥杯JAVA解法)

    题目描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和(路径上的每一步只可沿左斜线向下或右斜线向下走)。 输入描述 输入的第一行包含一个整数 N (1≤N≤

    2024年02月01日
    浏览(37)
  • 【编程题】有效三角形的个数

    给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。 示例1: 输入: nums = [2,2,3,4] 输出: 3 **解释:**有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3 示例2: 输入: nums = [4,2,3,4] 输出: 4 构成三角形的条件 :任意两条边之和大于第三边,其

    2024年02月11日
    浏览(44)
  • 数字三角形-蓝桥杯真题动态规划PYTHON解法

    目录 题目描述  解题思路 DP初始化 DP最终条件 DP初始条件 题目限制条件 总代码 首先映入我们眼帘的就是一个三角形,加求路径和最大,类似于找最短路径的题,很明显是一个二维数组的动态规划问题,对于动态规划问题我们只需要找好最终条件,初始条件(也就是特殊条件

    2024年02月09日
    浏览(36)
  • 蓝桥杯第十一届省赛——数字三角形(python组)

    题目:数字三角形 【问题描述】: 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最 大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边

    2023年04月10日
    浏览(45)
  • 蓝桥 卷“兔”来袭编程竞赛专场-03破解三角形密码 题解

    挑战介绍 三角形密码指的是将一串字符串按照正直角三角形的形状排列,传递的信息隐藏在每一行的最后一个字符,然后将所有的行的最后一个字符依次连接,就是需要传递的信息。 例如加密后的字符串是:我们爱的是蓝色的心桥 将加密字符串按照正直角三角形填充后如下

    2023年04月16日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包