luogu1216:数字三角形:递推元问题_21条线,共能数出多少个三角形,递推计数-程序员宅基地

技术标签: 递推元问题  题表  递推  题解  数字三角形  luogu  luogu1216  大礼包  元问题  

题目连接

  • 该题是luogu试炼场的2-12:T5

题目大意

  1. 给出 n, 给出一个 n 层的 正整数三角形,
  2. 从上往下,找一条线,要求和最大;
  3. 必须只能直接向下走,或者走右下角。

题目分析

  • 递推的元问题,可以从上往下顺推
  • 也可以从下往上,逆推


解题思路:

  1. a数组存原始数据,直接逆推,保证每个格子都是当前最优解
  2. 因为没有后效性,所以a [ 1 ] [ 1 ]就是答案

代码1:
//luogu1216:数字三角形,递推经典大水题 
//解题思路:
//1 从下往上扫一遍 
 
#include<cstdio>

int n;
int a[1010][1010];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			scanf("%d",&a[i][j]);
			
		}
	} 
	
	//从下往上 
	for(int i=n-1;i>=1;i--)
	{
		for(int j=1;j<=i;j++)
		{
			if(a[i+1][j]>a[i+1][j+1]) a[i][j]+=a[i+1][j];
			else a[i][j]+=a[i+1][j+1];
		}
	}
	
	printf("%d",a[1][1]);
	
	return 0; 
}








版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/liusu201601/article/details/89466608

智能推荐

历届试题 连号区间数-程序员宅基地

文章浏览阅读67次。/*问题描述小明这些天一直在思考这样一个奇怪而有趣的问题:在1~N的某个全排列中有多少个连号区间呢?这里所说的连号区间的定义是:如果区间[L, R] 里的所有元素(即此排列的第L个到第R个元素)递增排序后能得到一个长度为R-L+1的“连续”数列,则称这个区间连号区间。当N很小的时候,小明可以很快地算出答案,但是当N变大的时候,问题就不是那么简单了,现在小明需要你的帮助。输入格式...

Struts学习day3-OGNL-contextMap_map頧是gnlcontext-程序员宅基地

文章浏览阅读134次。一、contextMap中放的常用内容1、存放的常用内容request:存放的ServletRequest中的属性(attributes),他是一个Map&lt;String,Object&gt;session:存放的HttpSession中的属性(attributes),他是一个Map&lt;String,Object&gt;application:存放的ServletConte..._map頧是gnlcontext

前端工程师面试题汇总(我的解析,可能不一定对)(HTML部分)-程序员宅基地

文章浏览阅读148次。1、Doctype作用?严格模式与混杂模式如何区分?它们有何意义?HTML5 为什么只需要写 <!DOCTYPE HTML>?<!DOCTYPE> 的作用<!DOCTYPE> 声明必须是 HTML 文档的第一行,位于 <html> 标签之前。<!DOCTYPE> 声明不是 HTML 标签;它是指示 web 浏览器关于页面使..._在浏览器与预设格式一样可以使用哪种标签

同步、异步、阻塞、非阻塞IO总结(IO模型总结)_同步阻塞io 哪些地方会阻塞-程序员宅基地

文章浏览阅读2.2w次,点赞56次,收藏257次。知识点概念IO操作概念同步、异步(IO模型中的概念,并非并发模式中的同步、异步)阻塞、非阻塞同步IO模型异步IO模型读写(read write)与阻塞和非阻塞各种IO模型异同对比IO操作概念在Unix系统中,一切都是文件。文件就是流的概念,在进行信息的交流过程中,对这些流进行数据的收发操作就是IO操作我们都知道unix(like)世界里,一切皆文件,而文件是什么呢?文件就是一串二进制流而已..._同步阻塞io 哪些地方会阻塞

Android学习(七)—— Android布局-程序员宅基地

文章浏览阅读73次。Android布局1、LinearLayout线性布局,这种布局在平时的开发中用的最多,内部控件只能水平或竖直进行排列,在搭建较复杂的界面时会有点麻烦。常用属性android:orientation 控制控件排列方向,属性值为垂直(vertical)和水平(horizontal),默认水平方向。android:gravity:内部控件对齐方式,常用属性值有center、..._android 布局 中其中一个元素暂满父容器,另外一个只占用高度为20dp

【数论】狄利克雷卷积及其快速计算方法及杜教筛_快速狄利克雷卷积-程序员宅基地

文章浏览阅读1.8k次,点赞4次,收藏12次。背景本人即将去CTS&APIO2019,由于一些特殊原因,发现自己数论突然变得很菜。就决定在去的前一天,翻出来以前的数论学习资料看一看。翻到了czgj的校内狄利克雷卷积课件,发现其中提到了的任意数列f(n)f(n)f(n)和g(n)g(n)g(n)的狄利克雷卷积(f∗g)(n)(f*g)(n)(f∗g)(n)(从1到n,每一项都求出来)的求法。然而我没有反应过来。后来仔细想了想,发现..._快速狄利克雷卷积

随便推点

【历史上的今天】9 月 4 日:谷歌(Google) 23 周年;“人工智能之父” McCarthy 诞生_9月4日历史上的今天 科技时间-程序员宅基地

文章浏览阅读7.1k次,点赞22次,收藏9次。今天是 2021 年 9 月 4 日,在历史上的今天,柯达相机获得专利,从此成立相机帝国;人工智能之父 John McCarthy 出生;Google 公司正式成立,改变了许多人的命运。_9月4日历史上的今天 科技时间

1024 hello world_1024_hello_world-程序员宅基地

文章浏览阅读204次。1024程序员节是广大程序员的共同节日。1024是2的十次方,二进制计数的基本计量单位之一。针对程序员经常周末加班与工作日熬夜的情况,部分互联网机构倡议每年的10月24日为1024程序员节,在这一天建议程序员拒绝加班。 程序员就像是一个个1024,以最低调、踏实、核心的功能模块搭建起这个科技世界。1G=1024M,而1G与1级谐音,也有一级棒的意思。 程序员(英文Programmer)是从事前端、后端程序开发、系统运维、测试等的专业人员。一般将程序员分为程序设计人员和程序编码人员,但两..._1024_hello_world

dcmtk读写dicom文件头与文件内容_dcmimage.h-程序员宅基地

文章浏览阅读1k次。图像处理与VTK/ITK文章列表 #include <boost/archive/text_oarchive.hpp> #include <boost/archive/text_iarchive.hpp> #include <iostream> #include <sstream> #include <string>#i..._dcmimage.h

JSON技术-Gson将bean转换json确保数据的正确,使用FastJson将Json转换Bean_java gson bean to jsonobject-程序员宅基地

文章浏览阅读4.2k次,点赞3次,收藏5次。一 、各个JSON技术的简介和优劣1.json-libjson-lib最开始的也是应用最广泛的json解析工具,json-lib 不好的地方确实是依赖于很多第三方包,包括commons-beanutils.jar,commons-collections-3.2.jar,commons-lang-2.6.jar,commons-logging-1.1.1.jar,ezmorph-1.0._java gson bean to jsonobject

Centos下更新Python到3.x_centos更新python3-程序员宅基地

文章浏览阅读188次。Centos下更新Python到3.x安装wget下载新版本解压缩创建一个空的文件夹,用来安装编译并安装创建软链接配置 yum参考了知乎用户-爬上墙头大佬的文章。Carlos Blog大佬的内容会更全面一些,但是链接似乎会被墙掉,所以把一些问题写在了这里。安装wget# yum install wget下载新版本这里用的版本是 Python3.7.0# wget https://www.python.org/ftp/python/3.5.2/Python-3.7.0.tgz解压缩# t_centos更新python3

pandas对dataframe的数据列进行随机抽样(Random Sample of Columns):使用sample函数进行数据列随机抽样(有放回的随机抽样,replacement)_从dataframe中读取完整的一列值,如何实现随机取值-程序员宅基地

文章浏览阅读685次,点赞3次,收藏3次。pandas对dataframe的数据列进行随机抽样(Random Sample of Columns):使用sample函数进行数据列随机抽样(有放回的随机抽样,replacement)目录pandas对dataframe的数据列进行随机抽样(Random Sample of Columns):使用sample函数进行数据列随机抽样(有放回的随机抽样,replacement)#使用sample函数进行数据列随机抽样语法#仿真数据#使用sample函数进行数据列随机抽样(有放回的随机_从dataframe中读取完整的一列值,如何实现随机取值

推荐文章

热门文章

相关标签