之前看这题还是一头雾水,现在看:啊啊啊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 栈的更多相关文章
-
洛谷P1044 栈(Catalan数)
P1044 栈 题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表. 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈). 栈的重要 ...
-
洛谷——P1044 栈
P1044 栈——卡特兰数 题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表. 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈) ...
-
洛谷 p1044 栈 【Catalan(卡特兰数)】【经典题】
题目链接:https://www.luogu.org/problemnew/show/P1044 转载于:https://www.luogu.org/blog/QiXingZhi/solution-p ...
-
洛谷 - P1044 - 栈 - 简单dp
https://www.luogu.org/problemnew/show/P1044 由于是用标签搜索进来的,所以这道题一定是有dp的解法. 很显然规定每次加入元素之前可以从栈中清理出任意数量的元素 ...
-
洛谷 P1044 栈
题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表. 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈). 栈的重要性不言自明,任何 ...
-
洛谷P1044栈(DP)
题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表. 栈有两种最重要的操作,即poppoppop(从栈顶弹出一个元素)和pushpushpush(将一个元素进栈) ...
-
AC日记——栈 洛谷 P1044
题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表. 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈). 栈的重要性不言自明,任何 ...
-
洛谷 P1573 栈的操作
题目描述 现在有四个栈,其中前三个为空,第四个栈从栈顶到栈底分别为1,2,3,-,n.每一个栈只支持一种操作:弹出并压入.它指的是把其中一个栈A的栈顶元素x弹出,并马上压入任意一个栈B中.但是这样的操 ...
-
洛谷P1573 栈的操作 [2017年6月计划 数论11]
P1573 栈的操作 题目描述 现在有四个栈,其中前三个为空,第四个栈从栈顶到栈底分别为1,2,3,…,n.每一个栈只支持一种操作:弹出并 压入.它指的是把其中一个栈A的栈顶元素x弹出,并马上压入任意 ...
随机推荐
-
Linux下解压命令大全 解压缩 tar bz2 zip tar.gz gz
.tar解包:tar xvf FileName.tar打包:tar cvf FileName.tar DirName(注:tar是打包,不是压缩!)---------------.gz解压1:gunz ...
-
让VS2010支持HTML5
一.升级Microsoft Visual Studio 2010到Microsoft Visual Studio 2010 sp1 1.升级方法一这里直接给传送门了 Microsoft Visual ...
-
总结 XSS 与 CSRF 两种跨站攻击
前言 在那个年代,大家一般用拼接字符串的方式来构造动态 SQL 语句创建应用,于是 SQL 注入成了很流行的攻击方式.在这个年代, 参数化查询 [1] 已经成了普遍用法,我们已经离 SQL 注入很远了 ...
-
C++ 中的计时器
在Java中,有时候会要测试程序的性能,所以会采用System.currentTimeMillis()等类库函数去测试时间开销. 在C++中同样可以完成此功能. 头文件: #include<ct ...
-
[Oracle]审计Audit
1.Audit的概念 Audit是监视和记录用户对数据库进行的操作,以供DBA进行问题分析.利用Audit功能,可以完成以下任务: 监视和收集特定数据库活动的数据.例如管理员能够审计哪些表被更新,在某 ...
-
Exynos4412从SD卡启动的简单网络文件系统制作
Exynos4412从SD卡启动的简单网络文件系统制作 1. 简介 嵌入式系统能够在开发板上正常运行,需要先进行系统配置,一个完整的嵌入式系统应该包含的几个部分::uboot,kernel,rootf ...
-
XMPP系列(四)---发送和接收文字消息,获取历史消息功能
今天开始做到最主要的功能发送和接收消息.获取本地历史数据. 先上到目前为止的效果图: 首先是要在XMPPFramework.h中引入数据存储模块: //聊天记录模块的导入 # ...
-
document.querySelectorAll() 兼容 IE6
不多说,直接上代码 // 使用 css 选择器获取元素对象 兼容性封装 Test Already. function getElementsByCss(cssStr){ if(document.que ...
-
day 61 Django part-1 django的安装,以及初学者三件套(以及settings中的mysql配置)
我们的django到底是什么东西呢? 我们的代码都是在后台写的,包括我们的pycharm都是属于后台的工具,但是我们的后端开发说到底是需要开发完了之后拿到用户面前的,让我们的用户看到我们的东西,首先要 ...
-
mybatis 中between and用法
今天遇到一个问题,半天没看出来问题,特意记录一下 Dao ConfigEvaluation findConfigEvaluationByEvalpecent(BigDecimal evalPercen ...