一道巧妙的卡特兰数建模

题目

SKYLINE - Skyline

此题是左神的卡特兰数教程中的一道练习题目(这里强烈安利想学算法的同学可以看左神的教程),认真分析后发现实际上不难做,题意也很简单:

数字从1到n,可以形成很多排列,要求任意从左往右的三个位置,不能出现依次递增的样子。返回排列的方法数。也就是说不存在 i < j < k i<j<k i<j<k 并且满足 a [ i ] < a [ j ] < a [ k ] a[i]<a[j]<a[k] a[i]<a[j]<a[k]

思路

这道题目我首先的想法是用经典的卡特兰数模型去做一个映射,但是发现其中的问题结构和卡特兰数经典的组合结构差很多。

首先我们可以明确一点, n n n个数字的所有合法序列一定是从 n − 1 n-1 n1个数字的合法序列中某个位置插入 n n n得到(这个证明不难,这里省略)。

所以我们不妨枚举其中的最大的数字的位置来找一下规律,而且可以得知,最大数字的左边的所有数字一定是单调递减的(不然一定不合法),所以我们给合法的序列规定一个最长单调递减前缀的长度,举个例子:

3 , 2 , 1 3,2,1 3,2,1的最长单调递减前缀长度是3, 2 , 1 , 4 2,1,4 2,1,4的最长单调递减前缀长度是2,以此类推,这个在后面会有用。

构造

n = 1 n=1 n=1的时候,我们只有一种合法的序列:

1 1 1

n = 2 n=2 n=2的时候,我们可以枚举2的位置,得到一个合法的序列:

2 , 1 1 , 2 2,1 \\ 1,2 2,11,2

n = 3 n=3 n=3的时候,我们继续枚举3的位置,如果放在第一个位置上,就有:

3 , 2 , 1 3 , 1 , 2 3,2,1 \\ 3,1,2 3,2,13,1,2

都是合法的,如果放在第二个位置上,相当于插入了 n = 2 n=2 n=2的中间,则有:

2 , 3 , 1 1 , 3 , 2 2,3,1 \\ 1,3,2 2,3,11,3,2

也都是合法的,那么我们放到 n = 2 n=2 n=2的合法序列的最后面呢?

2 , 1 , 3 1 , 2 , 3 2,1,3 \\ 1,2,3 2,1,31,2,3

这个时候我们就会发现了, 1 , 2 , 3 1,2,3 1,2,3不合法!最重要的原因其实就是 1 , 2 1,2 1,2没有单调递减。而这也说明了一个非常重要的讯息:

对于 n − 1 n-1 n1个数字构成的最长单调递减前缀长度为 L L L的合法序列,最多能够贡献 L + 1 L+1 L+1 n n n个数字的合法序列。比如说下面这个例子:

序列 3 , 2 , 1 3,2,1 3,2,1,对于 4 4 4 4 4 4可以放到其中任何一个位置,得到:

4 , 3 , 2 , 1 3 , 4 , 2 , 1 3 , 2 , 4 , 1 3 , 2 , 1 , 4 4,3,2,1 \\ 3,4,2,1 \\ 3,2,4,1 \\ 3,2,1,4 4,3,2,13,4,2,13,2,4,13,2,1,4

本质就是 4 4 4的左边都是单调递减的。而对于序列 2 , 1 , 3 2,1,3 2,1,3而言,就只能得到以下的合法序列:

4 , 2 , 1 , 3 2 , 4 , 1 , 3 2 , 1 , 4 , 3 4,2,1,3 \\ 2,4,1,3 \\ 2,1,4,3 4,2,1,32,4,1,32,1,4,3

因此,我们将这个问题转换为了维护合法序列的最长单调递减长度的问题

维护

首先我们可以分析, n n n个数字的合法序列中,最长单调递减长度 L L L为1的合法序列有哪些?其实就是 n − 1 n-1 n1个数字的合法序列的数量。构造方法就是将 n n n放在所有序列的第一个数字后面。同理, L L L为2的合法序列长度等于 n − 1 n-1 n1个数字的合法序列中的所有 L ≥ 2 L \ge 2 L2的序列,构造方法就是放在第二个数字后面,以此类推。但是这里需要注意一点,如果将 n n n放在序列的第一个位置,那么一定能够使得所有序列的 L L L增加1,因此最后还要加上去,所以结论就是 n n n个数字的合法序列的最长单调递减长度为 L L L的合法序列个数等于 n − 1 n-1 n1个数字中的合法序列最长单调递减长度为 x ≥ L − 1 x \ge L-1 xL1的合法序列数量之和 。下面举例子说明:

这是 n = 3 n=3 n=3的所有合法序列以及 L L L的信息:

sequenceL
3,2,13
3,1,22
2,3,11
1,3,21
2,1,32

其中的 L L L的信息可以得到:

Lnumber
12
22
31

那么我们其实就可以了构造关于 n = 4 n=4 n=4 L L L表了(前缀和),先算 n n n不放在最前面的:

L = 1 L=1 L=1的情况,有 2 + 2 + 1 = 5 2+2+1=5 2+2+1=5种。
L = 2 L=2 L=2的情况,有 2 + 1 = 3 2+1=3 2+1=3种。
L = 3 L=3 L=3的情况,有 1 1 1种。
L = 4 L=4 L=4的情况,有 0 0 0种。

然后还有一种将 n n n放到最前面,这样将会使得我们现在的长度为 L L L的合法序列,加上之前的长度为 L − 1 L-1 L1的合法序列个数:

L = 1 L=1 L=1的情况,有 5 5 5种。
L = 2 L=2 L=2的情况,有 3 + 2 = 5 3+2=5 3+2=5种。
L = 3 L=3 L=3的情况,有 1 + 2 = 3 1+2=3 1+2=3种。
L = 4 L=4 L=4的情况,有 1 1 1种。

实际上可以使用上面的结论一步算完:

L = 1 L=1 L=1的情况,对应 x ≥ 0 x \ge 0 x0,有 2 + 2 + 1 = 5 2+2+1=5 2+2+1=5种。
L = 2 L=2 L=2的情况,对应 x ≥ 1 x \ge 1 x1,有 2 + 2 + 1 = 5 2+2+1=5 2+2+1=5种。
L = 3 L=3 L=3的情况,对应 x ≥ 2 x \ge 2 x2,有 1 + 2 = 3 1+2=3 1+2=3种。
L = 4 L=4 L=4的情况,对应 x ≥ 3 x \ge 3 x3,有 1 1 1种。

可以得到下面的表:

Lnumber
15
25
33
41

n n n个数字对应的合法序列个数就是以上的 n u m b e r number number的和。

卡特兰数建模

上面的 L L L表维护过程实际上可以用图可视化一下( n = 6 n=6 n=6):

[ 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 2 2 1 0 0 5 5 3 1 0 14 14 9 4 1 42 42 28 14 5 1 ] \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 2 & 2 & 1 \\ 0 & 0 & 5 & 5 & 3 & 1 \\ 0 & 14 & 14 & 9 & 4 & 1 \\ 42 & 42 & 28 & 14 & 5 & 1 \end{bmatrix} 000004200001442000514280025914012345111111

我们其实可以很容易发现,对于 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j + 1 ] f[i][j]=f[i-1][j]+f[i][j+1] f[i][j]=f[i1][j]+f[i][j+1],为什么呢?我们不妨这样看,第一行第一个1代表就是 L = 1 L=1 L=1的数量,第二行从左往右分别代表 L L L 1 1 1 2 2 2的数量,第三行从左到右分别代表 L L L 1 1 1 3 3 3的数量,以此类推。那么根据我们上面讨论的结论,可知:

f [ i ] [ j ] = ∑ k = j k = i − 1 f [ i − 1 ] [ k ] = f [ i − 1 ] [ j ] + ∑ k = j + 1 k = i − 1 f [ i − 1 ] [ k ] = f [ i − 1 ] [ j ] + f [ i ] [ j + 1 ] f[i][j]=\sum_{k=j}^{k=i-1}f[i-1][k]=f[i-1][j]+\sum_{k=j+1}^{k=i-1}f[i-1][k]=f[i-1][j]+f[i][j+1] f[i][j]=k=jk=i1f[i1][k]=f[i1][j]+k=j+1k=i1f[i1][k]=f[i1][j]+f[i][j+1]

得到这个表达式之后,那么这道题就很显然和卡特兰数的路径计数模型相关了!因为上面的矩阵的结果就是等于你每一步只能向下走或者向左走且不能超过对角线的方法数量!不能超过对角线的走法也就意味着任意时刻向下走的次数大于等于向左走,而这也就是卡特兰数的经典模型,所有后面也就不再赘述了,不懂的强烈推荐看看左神教程。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/459859.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

TIFS-2024 FIRe2:细粒度表示和重组在换衣行人重识别中的应用

总体结论 本文提出了一种新的细粒度表示与重构&#xff08;FIRe2&#xff09;框架&#xff0c;用于解决布变人重识别问题。通过细粒度特征挖掘和属性重构&#xff0c;FIRe2在不依赖任何辅助信息的情况下&#xff0c;实现了最先进的性能。该方法在多个基准数据集上取得了显著的…

一款专业获取 iOS 设备的 UDID 工具|一键获取iPhone iPad设备的 UDID

什么是UDID&#xff1f; UDID&#xff0c;是iOS设备的一个唯一识别码&#xff0c;每台iOS设备都有一个独一无二的编码&#xff0c;这个编码&#xff0c;我们称之为识别码&#xff0c;也叫做UDID&#xff08; Unique Device Identifier&#xff09; 扫描后系统提示输入密码&am…

HTML--浮动布局练习

<!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title><style>/* 整个浏览器页…

ES6 变量的解构赋值

数组的解构赋值 对象的解构赋值 字符串的解构赋值

利用游戏引擎的优势

大家好&#xff0c;我是小蜗牛。 在当今快速发展的游戏产业中&#xff0c;选择合适的游戏引擎对开发者来说至关重要。Cocos Creator作为一款功能强大且灵活的游戏引擎&#xff0c;为开发者提供了丰富的工具和资源&#xff0c;使他们能够高效地开发出优秀的游戏。本文将探讨如何…

Python+Selenium+Pytest+POM自动化测试框架封装(完整版)

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 1、测试框架简介 1&#xff09;测试框架的优点 代码复用率高&#xff0c;如果不使用框架的话&#xff0c;代码会显得很冗余。可以组装日志、报告、邮件等一些高…

【鸿蒙HarmonyOS实战:通过华为应用市场上架测试版App实现HBuilder X打包的UniApp项目的app转hap教程(邀请码)方式教程详解】

鸿蒙HarmonyOS实战&#xff1a;通过华为应用市场上架测试版App实现HBuilder X打包的UniApp项目的app转hap教程&#xff08;邀请码&#xff09;方式详解 在使用uniapp打包的鸿蒙项目的过程中&#xff0c;由于生成的是app文件&#xff0c;而hdc传给鸿蒙HarmonyOS系统需要的是hap文…

【Apache Zookeeper】

一、简介 1、场景 如何让⼀个应⽤中多个独⽴的程序协同⼯作是⼀件⾮常困难的事情。开发这样的应⽤&#xff0c;很容易让很多开发⼈员陷⼊如何使多个程序协同⼯作的逻辑中&#xff0c;最后导致没有时间更好地思考和实现他们⾃⼰的应⽤程序逻辑&#xff1b;又或者开发⼈员对协同…

名词(术语)了解--SSR/CSR

名词&#xff08;术语&#xff09;了解–SSR/CSR 什么是服务器端渲染(SSR)? 服务器端渲染是指由服务器生成完整的 HTML 页面&#xff0c;然后发送给客户端的过程。 这与客户端渲染&#xff08;CSR&#xff09;形成对比&#xff0c;后者主要依赖浏览器端的 JavaScript 来渲染…

有趣智力题(非编程题)

目录 赛马烧香问题 赛马 题目描述: 一共有36匹马 6个跑道 在没有计时器的情况下 请问: 最少进行多少次赛马 可以确定前三名? 答案:8次 图解思路: 注意下图写错了 注释没写错 图画错了 正确的是下图 烧香问题 题目描述: 有两根香 材质不均匀 但是每一根香 烧完都需要1h 请利用…

学习threejs,使用粒子实现下雪特效

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;threejs gis工程师 文章目录 一、&#x1f340;前言1.1 ☘️THREE.Points简介1.11 ☘️…

Golang | Leetcode Golang题解之第517题超级洗衣机

题目&#xff1a; 题解&#xff1a; func findMinMoves(machines []int) (ans int) {tot : 0for _, v : range machines {tot v}n : len(machines)if tot%n > 0 {return -1}avg : tot / nsum : 0for _, num : range machines {num - avgsum numans max(ans, max(abs(sum…

算法练习:209. 长度最小的子数组

题目链接&#xff1a;209. 长度最小的子数组。 这里ans来统计最小长度&#xff0c;所以初始值设置为INT_MAX.最后如果ans结果还是INT_MAX时&#xff0c;说明无此数组。 class Solution { public:int minSubArrayLen(int target, vector<int>& nums) {if (nums.size(…

WPF+MVVM案例实战(十一)- 环形进度条实现

文章目录 1、运行效果2、功能实现1、文件创建与代码实现2、角度转换器实现3、命名空间引用 3、源代码下载 1、运行效果 2、功能实现 1、文件创建与代码实现 打开 Wpf_Examples 项目&#xff0c;在Views 文件夹下创建 CircularProgressBar.xaml 窗体文件。 CircularProgressBa…

《贪婪算法实战:寻找最短无序连续子数组的深度解析与实现》

🚀 博主介绍:大家好,我是无休居士!一枚任职于一线Top3互联网大厂的Java开发工程师! 🚀 🌟 在这里,你将找到通往Java技术大门的钥匙。作为一个爱敲代码技术人,我不仅热衷于探索一些框架源码和算法技巧奥秘,还乐于分享这些宝贵的知识和经验。 💡 无论你是刚刚踏…

堆的基本概念和插入删除方法的介绍

优先级队列的介绍&#xff1a; 1.1优先级队列&#xff1a;优先级队列是一种特殊的队列数据结构&#xff0c;每个元素都有一个与之关联的优先级&#xff0c;与普通队列不同&#xff0c;优先级队列中的元素是按照优先级顺序进行处理的&#xff0c;而不是简单的插入。 特点&…

雷军:对“雷军语音包”感到不适,希望停止使用

对于社交媒体上频繁出现的“雷军AI语音包”&#xff0c;雷军发声回应。10月29日&#xff0c;雷军发布视频表示&#xff1a;“最近两年AI特别火&#xff0c;技术进步特别得快&#xff0c;前段时间我在刷抖音的时候&#xff0c;经常看到很多人在玩‘雷军AI’&#xff0c;就是雷军…

分布式光伏是什么意思?如何高效管理?

分布式光伏系统是指在用户现场或靠近用电现场配置较小的光伏发电供电系统&#xff0c;以满足特定用户的需求。根据通知&#xff0c;分布式光伏系统主要有以下几类定义&#xff1a; 10kV以下电压等级接入&#xff0c;且单个并网点总装机容量不超过6MW的分布式电源&#xff1a;这…

项目1 yolov5鱼苗检测计数

yolov5鱼苗检测 1. yolov5鱼苗检测1.1. 环境配置1.2 Predict1.3 Validate1.4 Train1.5 生成 ONNX 2 代码解析2.1 模型2.2 数据集2.3 损失函数2.4 训练2.5 预测 之前做的项目&#xff0c;再回顾一下 环境&#xff1a;GPU1卡&#xff0c;CPU4核&#xff0c;每显卡12GB&#xff0c…

智能文档处理平台:免费体验智能化医疗信息提取

前提&#xff1a;医疗行业信息碎片化问题普遍&#xff0c;手工数据录入效率低且易错&#xff0c;导致数据管理难度大。本系统可帮助医疗机构在信息管理上迈向智能化&#xff0c;优化流程并提升效率。 系统概述&#xff1a; 思通数科推出的智能文档处理系统&#xff0c;专为解…