当前位置: 首页 > news >正文

P1044 [NOIP2003 普及组] 栈题解

题目

有一个单端封闭的管子,将N(1<=N<=18)个不同的小球按顺序放入管子的一端。在将小球放入管子的过程中也可以将管子最顶上的一个或者多个小球倒出来。请问:倒出来的方法总数有多少种?

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例

3

输出样例

5

解析

假设i个元素一共有h[i]种出管方式。要求n个元素的出管方式,但是其中每一个元素(从1到n)都可能是最后一个出管的。假设第k个小球是最后一个出管的,比k早入管且早出管有k-1个数,一共有h[k-1]种出管方式;比k晚入管且早出管有n-k个数,一共有h[n-k]种出管方式。这种情况下一共就有h[k-1]*h[n-k]种出管方式。当k取不同值的时候,产生的出管序列也是独立的。所以可以加起来。k的取值范围可以是从1到n。所以递推式是h(n)=h(0)*h(n-1)+h(1)*h(n-2)+……+h(n-1)*h(0),初始条件是h[0]=h[1]=1。

#include<cstdio>
int main(){int n,h[20]={1,1};scanf("%d",&n);for(int i=2;i<=n;i++){for(int j=0;j<i;j++){h[i]+=h[j]*h[i-j-1];}}printf("%d",h[n]);return 0;
}

相关文章:

P1044 [NOIP2003 普及组] 栈题解

题目 有一个单端封闭的管子&#xff0c;将N(1<N<18)个不同的小球按顺序放入管子的一端。在将小球放入管子的过程中也可以将管子最顶上的一个或者多个小球倒出来。请问&#xff1a;倒出来的方法总数有多少种&#xff1f; 输入输出格式 输入格式 输入文件只含一个整数n…...

【DSP】数字信号处理发展里程碑(AI【文心一言】 辅助生成)

在远离尘嚣的学术殿堂中&#xff0c;数字信号处理&#xff08;DSP&#xff09;这一学科犹如一颗璀璨的明珠&#xff0c;其发展历程充满了传奇色彩。下面&#xff0c;就让我们一起穿越时空&#xff0c;回到那些激动人心的时刻&#xff0c;见证数字信号处理从无到有、从弱到强的壮…...

【JavaScript 】finally() 方法和Filter() 方法

JavaScript 中的finally() 方法 finally是 JavaScript 构造中使用的方法try-catch。try它在and阻塞之后执行catch&#xff0c;无论 Promise 是已履行还是已拒绝。该函数的主要作用是执行必要的清理任务并向用户传达消息。一个常见的用例可能是通知用户“您的请求已被处理”&am…...

假期作业8

线程和进程服务器 线程 #include <myhead.h>#define SIP "192.168.0.114" #define SPORT 8888void *task(void *arg){printf("客户端连接\n");sleep(1);pthread_exit(NULL); }int main(int argc, const char *argv[]) {int sfd socket(AF_INET, S…...

基于vue+node.js的校园跳蚤市场系统多商家

校园跳蚤市场系统可以在短时间内完成大量的数据处理、帮助用户快速的查找校园跳蚤市场相关信息&#xff0c;实现的效益更加直观。校园跳蚤市场系统中采用nodejs技术和mysql数据库。主要包括管理员、发布者和用户三大部分&#xff0c;主要功能是实现对个人中心、用户管理、发布者…...

Linux操作系统基础(六):Linux常见命令(一)

文章目录 Linux常见命令 一、命令结构 二、ls命令 三、cd命令 四、mkdir命令 五、touch命令 六、rm命令 七、cp命令 八、mv命令 九、cat命令 十、more命令 Linux常见命令 一、命令结构 command [-options] [parameter]说明: command : 命令名, 相应功能的英文单词…...

【Android-Compose】Material3 新版下拉刷新 PullRefresh

这里写自定义目录标题 1、&#xff08;新&#xff09;用于 Jetpack Compose 的刷新指示器1.1 SwipeRefresh 迁移到新的 PullRefresh1.2 迁移步骤1.3 自定义指示器 2、原始文档&#xff08;SwipeRefresh &#xff09;的使用依赖导入2.1 使用方法2.2 完整示例&#xff08;包括视图…...

FANUC机器人外部远程启动的相关参数设置示例

FANUC机器人外部远程启动的相关参数设置示例 如下图所示,在MENU---设置---选择程序中,设置程序选择模式:RSR(这个根据自己实际使用的自动启动方式来决定,你用RSR选RSR,用PNS就选PNS), 自动运行开始方法:选择UOP,即RSR1-RSR8的启动信号分别对应UI9-UI16, 最后,点击…...

供货商、品牌方、供应链如何对接快团团头部大团长?这三个关键点你一定要记住

供货商、品牌方、供应链如何对接快团团头部大团长&#xff1f;这三个关键点你一定要记住 有很多的品牌方、供应链、工厂在线上拿到了不少的社群快团团团长的资源&#xff0c;但是真正对接上的寥寥无几&#xff0c;哪怕自己的品做得非常好&#xff0c;但是都在这个行业触了霉头…...

LLMs之Llama2 70B:《Self-Rewarding Language Models自我奖励语言模型》翻译与解读

LLMs之Llama2 70B&#xff1a;《Self-Rewarding Language Models自我奖励语言模型》翻译与解读 目录 《Self-Rewarding Language Models》翻译与解读 Abstract 5 Conclusion结论 6 Limitations限制 《Self-Rewarding Language Models》翻译与解读 地址 文章地址&#xff1…...

电商小程序06用户审核

目录 1 创建自定义应用2 显示待办数量3 创建审核页面4 开发审核功能5 搭建布局6 最终效果总结 上一篇我们讲解了用户注册的功能&#xff0c;用户注册之后状态是待审核&#xff0c;需要管理员进行审核。通常给管理员提供一套PC端的软件进行相关的操作&#xff0c;在低代码中&…...

vue3跨组件(多组件)通信:事件总线【Event Bus】

★推荐方案&#xff1a;使用 events npm库&#xff1b; 可用范围&#xff1a;vue、react、angular等任何框架都可使用&#xff1b;且使用方式完全一致&#xff1b; 本文仅介绍、讲解对web页面端项目的常用API&#xff1b;通过events实现事件总线功能&#xff1b; event库概述&a…...

教材管理系统

文章目录 教材管理系统一、系统演示二、项目介绍三、系统部分功能截图四、部分代码展示五、底部获取项目源码&#xff08;9.9&#xffe5;带走&#xff09; 教材管理系统 一、系统演示 教材管理系统 二、项目介绍 语言&#xff1a;nodejs 框架&#xff1a;egg.js、Vue 数据库…...

PV、UV、IP

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言1. PV1.1 PV 计算1.2 PV 的影响因素 2. UV2.1 UV 计算2.2UV 的影响因素 3. IP3.1 IP和UV①UV大于IP②UV小于IP 三者的关系PV 和 UV 前言 PV、UV、IP是我们在运…...

ZigBee学习——在官方例程上实现串口通信

Z-Stack版本为3.0.2 IAR版本为10.10.1 文章目录 一、添加头文件二、定义接收缓冲区三、编写Uart初始化函数四、编写串口回调函数五、函数声明六、函数调用七、可能遇到的问题(function “halUartInit“ has no prototype) 以下所有操作都是在APP层进行&#xff0c;也就是这个文…...

nginx添加lua模块

目录 已安装了nginx&#xff0c;后追加lua模块nginx 重新编译知识参考&#xff1a; 从零安装一、首先需要安装必要的库&#xff08;pcre、zlib、openssl&#xff09;二、安装LUA环境及相关库 &#xff08;LuaJIT、ngx_devel_kit、lua-nginx-module&#xff09;注意&#xff1a;…...

Csapp-chapter3-压栈和弹栈

bp与sp&#xff08;压栈和弹栈&#xff09; 在计算机内部的寄存器组中&#xff0c;有一对寄存器非常有意思&#xff1a;%ebp&#xff0c;%esp 文章目录 bp与sp&#xff08;压栈和弹栈&#xff09;寄存器组示例图%ebp与%esp总结 寄存器组示例图 首先我们应该对于计算机中的寄存…...

Rust入门1——HelloWorld

文章目录 一、HelloWorld二、控制台输入 以最简单的两个Rust程序例子入门Rust。首先需要下载安装Rust&#xff0c;之后在VSCode或Clion中运行Rust需要下载Rust插件 一、HelloWorld fn main(){println!("Hello World!"); }二、控制台输入 use std::io::stdin; fn …...

android中使用Bitmp对象绘制图形

1、引言 你是否还在因为不懂UI设计而不得不去借用别人的图片&#xff0c;甚至使用各种网图作为界面布局的一部分&#xff0c;那么今天就教你使用Bitmap对象去绘制自定义图形&#xff0c;并保存为png格式的图片&#xff0c;须知图片编辑软件本就是程序员开发出来的&#xff0c;我…...

Linux操作系统基础(八):Linux的vi/vim编辑器

文章目录 Linux的vi/vim编辑器 一、vi/vim编辑器介绍 二、打开文件 三、VIM编辑器的三种模式(重点) 四、命令模式相关命令 五、底行模式相关命令 Linux的vi/vim编辑器 一、vi/vim编辑器介绍 vi是visual interface的简称, 是Linux中最经典的文本编辑器 vi的核心设计思想…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...