【动态规划】第十一届蓝桥杯省赛第二场C++ C组《数字三角形》(c++)

本文主要是介绍【动态规划】第十一届蓝桥杯省赛第二场C++ C组《数字三角形》(c++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.题目描述

上图给出了一个数字三角形。

从三角形的顶部到底部有很多条不同的路径。

对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。

此外,向左下走的次数与向右下走的次数相差不能超过 1。

2.输入格式

输入的第一行包含一个整数 N,表示三角形的行数。

下面的 N 行给出数字三角形。

数字三角形上的数都是 0 至 100 之间的整数。

3.输出格式

输出一个整数,表示答案。

4.数据范围

1≤N≤100

5.输入样例

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

6.输出样例

27

7.思路

动态规划

1.状态表示 :f[i][j]表示所有从头开始往下走到第i层第j个的路径的最大值

2.状态计算 :f[i][j] = max(f[i-1][j],f[i-1][j-1]) + value[i][j];

8.代码

#include<iostream>
using namespace std;
const int N = 110;
int n;int f[N][N];
int value[N][N];
int main()
{scanf("%d",&n);for(int i = 1; i<=n; i++)for(int j = 1; j <=i; j++)scanf("%d",&value[i][j]);for(int i = 1; i<= n; i++)for(int j = 1; j <=i; j++)f[i][j] = max(f[i-1][j],f[i-1][j-1]) + value[i][j];//n为偶数时,最后一层落在的点一定在n/2或n/2+1//n为奇数时,最后一层落在的点一定在n/2+1if(n % 2 == 0) printf("%d\n", max(f[n][n/2],f[n][n/2+1]));else printf("%d\n", f[n][n/2+1]);return 0;
}

这篇关于【动态规划】第十一届蓝桥杯省赛第二场C++ C组《数字三角形》(c++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/774882

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示