蓝桥杯 ALGO-124 数字三角形

红太狼 2022-08-19 11:08 230阅读 0赞

算法训练 数字三角形

时间限制：1.0s 内存限制：256.0MB

问题描述

（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路  
　　径，使该路径所经过的数字的总和最大。  
　　●每一步可沿左斜线向下或右斜线向下走；  
　　●1＜三角形行数≤100；  
　　●三角形中的数字为整数0，1，…99；  
  
  
　　 ![RequireFile.do_fid_9RdAy6Be][].  
　　（图３.１－１）

输入格式

文件中首先读到的是三角形的行数。  
  
　　接下来描述整个三角形

输出格式

最大总和（整数）

样例输入

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

样例输出

30

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int map[101][101];
    int main()
    {
    	int TT;
    	while(scanf("%d",&TT)!=EOF)
    	{
    		int i,j;
    		for(i=0;i<TT;i++)
    		{
    			j=i;
    			int yy;
    			yy=0;
    			while(j>=0)
    			{
    				scanf("%d",&map[i][i-yy]);
    				j--;
    				yy++;
    			}
    		}
    		for(i=TT-2;i>=0;i--)
    		{
    			int yy=i;
    			for(j=0;j<=yy;j++)
    			{
    				map[i][j]+=max(map[i+1][j],map[i+1][j+1]);
    			}
    		}
    		printf("%d\n",map[0][0]);
    	}
    	return 0;
    }

[RequireFile.do_fid_9RdAy6Be]: http://lx.lanqiao.org/RequireFile.do?fid=9RdAy6Be

发表评论取消回复

表情：

评论列表（有 0 条评论，230人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯算法训练之数字三角形（dp）

算法训练数字三角形时间限制：1.0s 内存限制：256.0MB 问题描述　　（图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路　　

缺乏、安全感/ 2024年02月17日 19:13/ 0 赞/ 73 阅读

相关蓝桥杯算法训练 ALGO-124 数字三角形

算法训练数字三角形时间限制：1.0s 内存限制：256.0MB 问题描述　　（图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路　径

太过爱你忘了你带给我的痛/ 2023年10月06日 09:38/ 0 赞/ 88 阅读

相关【蓝桥杯】ALGO-86 矩阵乘法

资源限制时间限制：1.0s 内存限制：512.0MB 问题描述　　输入两个矩阵，分别是ms，sn大小。输出两个矩阵相乘的结果。输入格式　　第一行，空

谁践踏了优雅/ 2022年12月04日 07:42/ 0 赞/ 190 阅读

相关蓝桥杯-算法训练：ALGO-49 JAVA

问题描述: 　　对于给定整数数组a[],寻找其中最大值，并返回下标。输入格式　　整数数组a[],数组元素个数小于1等于100。输出数据分作

傷城~/ 2022年11月11日 15:54/ 0 赞/ 416 阅读

相关蓝桥杯 ALGO-92 前缀表达式

算法训练前缀表达式时间限制：1.0s 内存限制：512.0MB 问题描述　　编写一个程序，以字符串方式输入一个前缀表达式，然后计算它的值。输入格式为：“运算符对象

￡神魔★判官ぃ/ 2022年08月19日 11:19/ 0 赞/ 226 阅读

相关蓝桥杯 ALGO-97 排序

算法训练排序时间限制：1.0s 内存限制：512.0MB 问题描述　　编写一个程序，输入3个整数，然后程序将对这三个整数按照从大到小进行排列。　　输入格式：输

迷南。/ 2022年08月19日 11:19/ 0 赞/ 218 阅读

相关蓝桥杯 ALGO-101 图形显示

算法训练图形显示时间限制：1.0s 内存限制：512.0MB 问题描述　　编写一个程序，首先输入一个整数，例如5，然后在屏幕上显示如下的图形（5表示行数）：　

男娘i/ 2022年08月19日 11:14/ 0 赞/ 212 阅读

相关蓝桥杯 ALGO-124 数字三角形

算法训练数字三角形时间限制：1.0s 内存限制：256.0MB 问题描述　　（图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路　　

红太狼/ 2022年08月19日 11:08/ 0 赞/ 231 阅读

相关蓝桥杯--数字排列

蓝桥杯--数字排列今有7对数字：两个1，两个2，两个3，...两个7，把它们排成一行。要求，两个1间有1个其它数字，两个2间有2个其它数字，以此类推，两个7之间

蔚落/ 2022年05月29日 05:28/ 0 赞/ 202 阅读

相关蓝桥杯纸牌三角形

A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。下图就是一种排法（如有对齐问题，参看p1.p

怼烎@/ 2022年03月10日 10:50/ 0 赞/ 172 阅读