洛谷P1044 栈

时间:2022-08-26 19:35:39

之前看这题还是一头雾水,现在看:啊啊啊lydnb!

思考了一段时间,发现可以用DP。

令f[i]表示有i辆车时的方案数。

我一开始考虑的是在后面加车,可是这样搞不出状态转移方程来。

然后我考虑从前面加,问题迎刃而解!

考虑加在前面的那一辆车的出栈时机,这样就可以用 f[前] * f[后] 来转移了。

 #include <cstdio>
typedef long long LL;
const int N = ; LL f[N]; int main() {
int n;
scanf("%d", &n);
f[] = f[] = ;
for(int i = ; i <= n; i++) {
for(int j = ; j < i; j++) {
f[i] += f[j] * f[i - - j];
}
}
printf("%lld", f[n]);
return ;
}

AC代码

洛谷P1044 栈的更多相关文章

  1. 洛谷P1044 栈(Catalan数)

    P1044 栈 题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表. 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈). 栈的重要 ...

  2. 洛谷——P1044 栈

    P1044 栈——卡特兰数 题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表. 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈) ...

  3. 洛谷 p1044 栈 【Catalan(卡特兰数)】【经典题】

    题目链接:https://www.luogu.org/problemnew/show/P1044 转载于:https://www.luogu.org/blog/QiXingZhi/solution-p ...

  4. 洛谷 - P1044 - 栈 - 简单dp

    https://www.luogu.org/problemnew/show/P1044 由于是用标签搜索进来的,所以这道题一定是有dp的解法. 很显然规定每次加入元素之前可以从栈中清理出任意数量的元素 ...

  5. 洛谷 P1044 栈

    题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表. 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈). 栈的重要性不言自明,任何 ...

  6. 洛谷P1044栈(DP)

    题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表. 栈有两种最重要的操作,即poppoppop(从栈顶弹出一个元素)和pushpushpush(将一个元素进栈) ...

  7. AC日记——栈 洛谷 P1044

    题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表. 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈). 栈的重要性不言自明,任何 ...

  8. 洛谷 P1573 栈的操作

    题目描述 现在有四个栈,其中前三个为空,第四个栈从栈顶到栈底分别为1,2,3,-,n.每一个栈只支持一种操作:弹出并压入.它指的是把其中一个栈A的栈顶元素x弹出,并马上压入任意一个栈B中.但是这样的操 ...

  9. 洛谷P1573 栈的操作 &lbrack;2017年6月计划 数论11&rsqb;

    P1573 栈的操作 题目描述 现在有四个栈,其中前三个为空,第四个栈从栈顶到栈底分别为1,2,3,…,n.每一个栈只支持一种操作:弹出并 压入.它指的是把其中一个栈A的栈顶元素x弹出,并马上压入任意 ...

随机推荐

  1. Linux下解压命令大全 解压缩 tar bz2 zip tar&period;gz gz

    .tar解包:tar xvf FileName.tar打包:tar cvf FileName.tar DirName(注:tar是打包,不是压缩!)---------------.gz解压1:gunz ...

  2. 让VS2010支持HTML5

    一.升级Microsoft Visual Studio 2010到Microsoft Visual Studio 2010 sp1 1.升级方法一这里直接给传送门了 Microsoft Visual ...

  3. 总结 XSS 与 CSRF 两种跨站攻击

    前言 在那个年代,大家一般用拼接字符串的方式来构造动态 SQL 语句创建应用,于是 SQL 注入成了很流行的攻击方式.在这个年代, 参数化查询 [1] 已经成了普遍用法,我们已经离 SQL 注入很远了 ...

  4. C&plus;&plus; 中的计时器

    在Java中,有时候会要测试程序的性能,所以会采用System.currentTimeMillis()等类库函数去测试时间开销. 在C++中同样可以完成此功能. 头文件: #include<ct ...

  5. &lbrack;Oracle&rsqb;审计Audit

    1.Audit的概念 Audit是监视和记录用户对数据库进行的操作,以供DBA进行问题分析.利用Audit功能,可以完成以下任务: 监视和收集特定数据库活动的数据.例如管理员能够审计哪些表被更新,在某 ...

  6. Exynos4412从SD卡启动的简单网络文件系统制作

    Exynos4412从SD卡启动的简单网络文件系统制作 1. 简介 嵌入式系统能够在开发板上正常运行,需要先进行系统配置,一个完整的嵌入式系统应该包含的几个部分::uboot,kernel,rootf ...

  7. XMPP系列&lpar;四)---发送和接收文字消息,获取历史消息功能

    今天开始做到最主要的功能发送和接收消息.获取本地历史数据. 先上到目前为止的效果图:              首先是要在XMPPFramework.h中引入数据存储模块: //聊天记录模块的导入 # ...

  8. document&period;querySelectorAll&lpar;&rpar; 兼容 IE6

    不多说,直接上代码 // 使用 css 选择器获取元素对象 兼容性封装 Test Already. function getElementsByCss(cssStr){ if(document.que ...

  9. day 61 Django part-1 django的安装&comma;以及初学者三件套&lpar;以及settings中的mysql配置&rpar;

    我们的django到底是什么东西呢? 我们的代码都是在后台写的,包括我们的pycharm都是属于后台的工具,但是我们的后端开发说到底是需要开发完了之后拿到用户面前的,让我们的用户看到我们的东西,首先要 ...

  10. mybatis 中between and用法

    今天遇到一个问题,半天没看出来问题,特意记录一下 Dao ConfigEvaluation findConfigEvaluationByEvalpecent(BigDecimal evalPercen ...