当前位置: 首页 > 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的核心设计思想…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...