P1044 [NOIP2003 普及组] 栈 C语言

P1044 [NOIP2003 普及组] 栈 - 洛谷 | 计算机科学教育新生态

题目背景

栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈)。

栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。

宁宁考虑的是这样一个问题:一个操作数序列,1,2,…,n(图示为 1 到 3 的情况),栈 A 的深度大于 n。

现在可以进行两种操作,

  1. 将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作)
  2. 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作)

使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由 1 2 3 生成序列 2 3 1 的过程。

你的程序将对给定的 n,计算并输出由操作数序列 1, 2, …, n 经过操作可能得到的输出序列的总数。

输入格式

输入文件只含一个整数 n(1 ≤ n ≤ 18)。

输出格式

输出文件只有一行,即可能输出序列的总数目。

输入输出样例
输入 #1输出 #1
35
说明/提示

【题目来源】

NOIP 2003 普及组第三题

思路:

动态方程先写一下 

            if(i >= 1)//栈内有东西,可以出栈操作  和 进栈操作 
            dp[i][j] = dp[i-1][j] + dp[i+1][j-1];  
            if(i == 0)//进栈操作 
            dp[i][j] = dp[i+1][j-1]; 

用dp既可以做出来,思路过程先说说。f[i][j],i作为栈内元素个数,j为队列元素个数。有些人可能会觉得,为什么啊?状态方程为什么可以这样列呢?所以我们需要进行模拟队列1 2 3的过程,发现一点规律,这里我就不多说了。最终可以发现这两个条件的确可以确定组成序列的方案数。注意:f[i][0]都设置为1作为边界,是因为序列已经形成了,在搜索写法表示返回1.总之就是找到这个方案了返回1.dp也一样.
代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
int n;
int dp[20][20];//i表示栈内个数,j表示队列个数 ,那么方案数就是f[0][n] 
int main() 
{ 
  	cin >> n;
  	for(int i = 0 ; i <= n ; i++)
  	dp[i][0] = 1;//因为队列为0说明序列已经形成了,可以返回1了。 
  	for(int j = 1 ; j <= n ; j++)
  	{
  		for(int i = 0 ; i <= n ; i++)
		{
			if(i >= 1)//栈内有东西,可以出栈操作  和 进栈操作 
			dp[i][j] = dp[i-1][j] + dp[i+1][j-1];  
			if(i == 0)//进栈操作 
			dp[i][j] = dp[i+1][j-1]; 	
		}	
	}
	cout << dp[0][n];
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/962087.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基础项目实战——学生管理系统(c++)

目录 前言一、功能菜单界面二、类与结构体的实现三、录入学生信息四、删除学生信息五、更改学生信息六、查找学生信息七、统计学生人数八、保存学生信息九、读取学生信息十、打印所有学生信息十一、退出系统十二、文件拆分结语 前言 这一期我们来一起学习我们在大学做过的课程…

OpenEuler学习笔记(十七):OpenEuler搭建Redis高可用生产环境

在OpenEuler上搭建Redis高可用生产环境&#xff0c;通常可以采用Redis Sentinel或Redis Cluster两种方式&#xff0c;以下分别介绍两种方式的搭建步骤&#xff1a; 基于Redis Sentinel的高可用环境搭建 安装Redis 配置软件源&#xff1a;可以使用OpenEuler的默认软件源&#…

Python的那些事第六篇:从定义到应用,Python函数的奥秘

新月人物传记&#xff1a;人物传记之新月篇-CSDN博客 目录 一、函数的定义与调用 二、函数的参数 三、返回值&#xff08;return语句&#xff09; 四、作用域 五、匿名函数&#xff08;lambda表达式&#xff09; 六、总结 Python函数的奥秘&#xff1a;从定义到应用 编程…

vue3的路由配置

先找到Layout布局文件&#xff0c;从中找到左侧边栏&#xff0c;找到下述代码 <SidebarItem v-for"route in noHiddenRoutes" :key"route.path" :item"route" :base-path"route.path" />/** *菜单项 <SidebarItem>: *使用…

VLLM性能调优

1. 抢占 显存不够的时候&#xff0c;某些request会被抢占。其KV cache被清除&#xff0c;腾退给其他request&#xff0c;下次调度到它&#xff0c;重新计算KV cache。 报这条消息&#xff0c;说明已被抢占&#xff1a; WARNING 05-09 00:49:33 scheduler.py:1057 Sequence gr…

Blazor-@bind

数据绑定 带有 value属性的标记都可以使用bind 绑定&#xff0c;<div>、<span>等非输入标记&#xff0c;无法使用bind 指令的&#xff0c;默认绑定了 onchange 事件&#xff0c;onchange 事件是指在输入框中输入内容之后&#xff0c;当失去焦点时执行。 page &qu…

H264原始码流格式分析

1.H264码流结构组成 H.264裸码流&#xff08;Raw Bitstream&#xff09;数据主要由一系列的NALU&#xff08;网络抽象层单元&#xff09;组成。每个NALU包含一个NAL头和一个RBSP&#xff08;原始字节序列载荷&#xff09;。 1.1 H.264码流层次 H.264码流的结构可以分为两个层…

Qt中QVariant的使用

1.使用QVariant实现不同类型数据的相加 方法&#xff1a;通过type函数返回数值的类型&#xff0c;然后通过setValue来构造一个QVariant类型的返回值。 函数&#xff1a; QVariant mainPage::dataPlus(QVariant a, QVariant b) {QVariant ret;if ((a.type() QVariant::Int) &a…

C++,STL 简介:历史、组成、优势

文章目录 引言一、STL 的历史STL 的核心组成三、STL 的核心优势四、结语进一步学习资源&#xff1a; 引言 C 是一门强大且灵活的编程语言&#xff0c;但其真正的魅力之一在于其标准库——尤其是标准模板库&#xff08;Standard Template Library, STL&#xff09;。STL 提供了…

每日一题——序列化二叉树

序列化二叉树 BM39 序列化二叉树题目描述序列化反序列化 示例示例1示例2 解题思路序列化过程反序列化过程 代码实现代码说明复杂度分析总结 BM39 序列化二叉树 题目描述 请实现两个函数&#xff0c;分别用来序列化和反序列化二叉树。二叉树的序列化是将二叉树按照某种遍历方式…

关于安卓greendao打包时报错问题修复

背景 项目在使用greendao的时候&#xff0c;debug安装没有问题&#xff0c;一到打包签名就报了。 环境 win10 jdk17 gradle8 项目依赖情况 博主的greendao是一个独立的module项目&#xff0c;项目目前只适配了java&#xff0c;不支持Kotlin。然后被外部集成。greendao版本…

Java实现.env文件读取敏感数据

文章目录 1.common-env-starter模块1.目录结构2.DotenvEnvironmentPostProcessor.java 在${xxx}解析之前执行&#xff0c;提前读取配置3.EnvProperties.java 这里的path只是为了代码提示4.EnvAutoConfiguration.java Env模块自动配置类5.spring.factories 自动配置和注册Enviro…

【AutoSar】汽车诊断标准协议UDS详解

目录 一、基本概念二、UDS诊断协议2.1 诊断服务的概念2.2常用的诊断服务2.2.1 诊断会话控制服务&#xff08;10服务&#xff09;2.2.2 会话访问0x27服务2.2.3 用于读写的DID的0x22/0x2E服务 一、基本概念 车辆的诊断需要有Tester端和ECU段通过应答的方式进行通信&#xff0c;他…

Java线程认识和Object的一些方法

本文目标&#xff1a; 要对Java线程有整体了解&#xff0c;深入认识到里面的一些方法和Object对象方法的区别。认识到Java对象的ObjectMonitor&#xff0c;这有助于后面的Synchronized和锁的认识。利用Synchronized wait/notify 完成一道经典的多线程题目&#xff1a;实现ABC…

【漫话机器学习系列】067.希腊字母(greek letters)-写法、名称、读法和常见用途

希腊字母&#xff08;Greek Letters&#xff09; 希腊字母在数学、科学、工程学和编程中广泛使用&#xff0c;常用于表示变量、常量、参数、角度等。以下是希腊字母的完整列表及其常见用途。 大写与小写希腊字母表 大写小写名称&#xff08;英文&#xff09;名称&#xff08;…

【Block总结】OutlookAttention注意力,捕捉细节和局部特征|即插即用

论文信息 标题: VOLO: Vision Outlooker for Visual Recognition作者: Li Yuan, Qibin Hou, Zihang Jiang, Jiashi Feng, Shuicheng Yan代码链接: https://github.com/sail-sg/volo论文链接: https://arxiv.org/pdf/2106.13112 创新点 前景注意力机制: VOLO引入了一种称为“…

Linux Samba 低版本漏洞(远程控制)复现与剖析

目录 前言 漏洞介绍 漏洞原理 产生条件 漏洞影响 防御措施 复现过程 结语 前言 在网络安全的复杂生态中&#xff0c;系统漏洞的探索与防范始终是保障数字世界安全稳定运行的关键所在。Linux Samba 作为一款在网络共享服务领域应用极为广泛的软件&#xff0c;其低版本中…

hive:基本数据类型,关于表和列语法

基本数据类型 Hive 的数据类型分为基本数据类型和复杂数据类型 加粗的是常用数据类型 BOOLEAN出现ture和false外的其他值会变成NULL值 没有number,decimal类似number 如果输入的数据不符合数据类型, 映射时会变成NULL, 但是数据本身并没有被修改 创建表 创建表的本质其实就是在…

Elasticsearch的开发工具(Dev Tools)

目录 说明1. **Console**2. **Search Profiler**3. **Grok Debugger**4. **Painless Lab**总结 说明 Elasticsearch的开发工具&#xff08;Dev Tools&#xff09;在Kibana中提供了多种功能强大的工具&#xff0c;用于调试、优化和测试Elasticsearch查询和脚本。以下是关于Cons…

Qt中Widget及其子类的相对位置移动

Qt中Widget及其子类的相对位置移动 最后更新日期&#xff1a;2025.01.25 下面让我们开始今天的主题… 一、开启篇 提出问题&#xff1a;请看上图&#xff0c;我们想要实现的效果是控件黄色的Widge&#xff08;m_infobarWidget&#xff09;t随着可视化窗口&#xff08;m_glWidge…