洛谷 - P1044 - 栈 - 简单dp
2024-09-01 11:06:57
https://www.luogu.org/problemnew/show/P1044
由于是用标签搜索进来的，所以这道题一定是有dp的解法。
很显然规定每次加入元素之前可以从栈中清理出任意数量的元素。每一个元素都会贡献一种不同的排法。
试一下。进栈的顺序是1,2,3,...,n，那么可以设计dp[i]表示i为栈顶的方法数？这样没办法表示栈中元素的数量。
设计dp[i][j]表示i为栈顶，元素个数为j个的方法数，这样就记录了所有的信息。dp[0][0]表示空栈。
转移的话就很好想，每次向栈中加入新的元素i，那么dp[i][j]=sum(dp[0~i-1][j-1~n])，复杂度有点高，4次方呢。不过n取18的话就够用了。
但是这样好像得不到正确答案，会重复计数……还是说最后只计算n为栈顶的所有结果？
设计一个dp[i][j][k]，考虑前i个元素，以j为栈顶，k个元素的栈的方法，就变成了n的6次方……
还是看题解了，题解说这个是卡特兰数……好吧组合数学没学好……
设计dp[i]表示，第i个数的选法。
dp[0]=1,dp[1]=1
最新文章
- SQL Server数据库性能优化技巧
- php 正则匹配中文(转)
- 推荐！国外程序员整理的 PHP 资源大全
- c#之习题
- IOS 多线程编程之Grand Central Dispatch(GCD)介绍和使用 多线程基础和练习
- 导出项目为jar包
- linux下实现自己的shell解释器
- 【Chromium中文文档】线程
- POJ 3311 Hie with the Pie （BFS+最短路+状态压缩）
- [ios2]发布时去除NSLog打印
- YII框架视图模块化
- bootstrap: 内联表单；
- ifconfig和ping
- python将字符串转换成整型
- hdu 5776 抽屉定理
- 2019.02.16 bzoj5466: [Noip2018]保卫王国（链分治+ddp）
- node中中间件body-parser的实现方式
- python文档生成工具：pydoc、sphinx；django如何使用sphinx？
- 如何使用Maven scope
- 韩剧TV APP案例分析