[蓝桥杯 2019 国 B] 排列数

devtools/2024/12/24 2:11:10/

目录

前言

题解

思路

疑问

解答


前言

对于本篇文章是站在别人的基础之上来写的,对于这道题作为2019年国赛B组的最难的一题,他的难度肯定是不小的,这道题我再一开始接触的时候连思路都没有,也是看了两三遍别人发的题解,才慢慢明白了怎么去写。那么对于题解我就直接引用别人的优秀题解,但后再加上我对题解写的不详细的地方进行尽可能详细的描述补充。

题解

以下题解全来自洛谷

思路

设状态 dp[i][j]dp[i][j] 其中 ii 表示前 ii 个数中,有 jj 个折点的方案数。

考虑状态转移,显然 dp[i][j]dp[i][j] 只能影响到 dp[i+1][j]dp[i+1][j]、dp[i+1][j+1]dp[i+1][j+1]、dp[i+1][j+2]dp[i+1][j+2],证明如下:

首先需要确定,在原序列中插入第 i+1i+1 个数,这个 i+1i+1 是所有数中最大的,所以只要在非头/尾部插入这个点,这个点一定就是新的折点。

  1. dp[i+1][j]dp[i+1][j] 表示插入第 i+1i+1 个点后没有新增折点:

    例:

    情况一如图,当 i+1i+1 插入波峰 xx 左右侧时,xx 不再是折点,折点变成了 i+1i+1,此时折点数不变。

    情况二如图,当 i+1i+1 插入序列头尾 xx 左右时,xx 依然不是折点,序列没有新增折点,此时折点数不变(如果头或尾的点是向下走的那么插入后新增了一个点,不属于该范围,此时只有在其中一边插入 i+1i+1 才能满足不增加新折点)。

  2. dp[i+1][j+1]dp[i+1][j+1] 表示插入第 i+1个点后新增了一个转折点。

    只有一种情况,即当在序列头和尾向下走时在头和尾前后插入 i+1只增加一个转折点,如图,xx 为新增的一个转折点。

    所以转移方程:

    dp[i+1][j+1]=dp[i][j]×2dp[i+1][j+1]=dp[i][j]×2
  3. dp[i+1][j+2]dp[i+1][j+2] 表示插入第 i+1 个点后新增了两个转折点。

    显然在除了以上所有情况,其他地方插入 i+1i+1 都会新增两个折点,转移方程:

初始值:dp[1][0]=1dp[1][0]=1、dp[i][0]=2(1<i<n)dp[i][0]=2(1<i<n)。

答案:dp[n][k−1]dp[n][k−1]。

疑问

我问的疑问的地方就是我上面标红的地方以及图片插入的地方,是由这些地方而引出的疑问。

1>:为什么只在波峰处的左右插入?在峰谷处插入不符合?为什么呢?

2>:为什么第一种情况下的公式,为什么奇数情况下是j-1/2,偶数下是j/2?

 3>:插入第 i+1 个点后新增了一个转折点,这种情况按照如图所表示,他应该是只由特殊情况下,只会增加二啊,为什么用公式总结下来是直接*2呢?

就比如这种情况,我也没在头尾处插入啊?那他这种情况也是属于增加了一个转折点啊?

 4>:对于题解中的第三种情况是什么呢?

解答

相信你看完上面的四个疑问,心里肯定会有所疑问,那也相信通过你自己的思考,肯定会解决一两个疑问。无论如何,下面就由我来为大家解决四个疑问。

疑问一 :为什么只在波峰处的左右插入?在峰谷处插入不符合?为什么呢?

其实这个疑问人家题解也说的很明确了,也解释了在波峰处插入确实不会增加转折点,但我还是要说一点,这里人家只说是在波峰的左右处插入,没有说在峰谷插入的问题,这个一定要注意。而且在疑问三中,我也用图解释了在峰谷处插入也确实是会增加一个转折点的。所以不增加转折点的插入方法就只有两种情况,也就是题解说的两种情况。

疑问二: 为什么第一种情况下的公式,为什么奇数情况下是j-1/2,偶数下是j/2?

关于这个疑问,我们首先要知道一个结论:当转折点是奇数时:转折点数=峰谷+波峰=波峰*2+1/峰谷*2+1(相差不超过1。这是因为在一个排列中,波峰和峰谷是交替出现的。例如,如果一个排列从一个波峰开始,那么接下来可能是一个峰谷,然后再是一个波峰

当转折点时偶数时:峰谷=波峰

 这可以通过大量的举例来观察得到。我这里就简单的给大家简单的证明一下

首先我们假设,他的头与尾都是朝上的情况,大致如图所示

那么如果图中有一个波峰,那么他一定是比他的左右都是大的(图略有粗糙,能看明白就行)

假如这个波峰的高度是小于两边的高度的,那他还是会至少存在两个峰谷的。

假如这个波峰的高度在两边高度之间,那么同样因为存在一个波峰的原因,他至少会存在两个峰谷。

假如这个波峰的高度高于两边的高度,那么这时候会存在两种情况,第一种情况是没有峰谷,还有一种情况就是至少存在两个峰谷。

以次类推,在讨论当两边的头尾是向下的情况,

 如果在中间插入一个波峰

然后再分三种情况,与两边的高度做套路

假设他的高度高于两边,那么峰谷的数量为0,或者至少为两个

假设他的高度再二者中间,那么必定还存在一个与之相对应的波峰,还有中间存在一个峰谷。

假设他的高度再二者之下,那么,那么他必有一个向下的调整,那么对于这种情况,他必定会至少由三个波峰,两个峰谷。

 对于上面的解释说明肯定说的不是很清楚,但是只要知道一点:

当转折点是奇数时:转折点数=峰谷+波峰=波峰*2+1/峰谷*2+1(相差不超过1。这是因为在一个排列中,波峰和峰谷是交替出现的。例如,如果一个排列从一个波峰开始,那么接下来可能是一个峰谷,然后再是一个波峰

当转折点时偶数时:峰谷=波峰

 所以公式中也就是用 j-1/2 来计算的。

疑问三:插入第 i+1 个点后新增了一个转折点,这种情况按照如图所表示,他应该是只由特殊情况下,只会增加二啊,为什么用公式总结下来是直接*2呢?

 关于这个疑问,也是我疑惑时间最长的。

但想明白了其实还是蛮简单的,其实就是题解描述的不够清楚,

这个只是不同构型下会产生不同的结果,但是这个加的位置也就是题解里考虑的范围,硬要说就是题解表述不完全,没有对全部构型画图。

注意:人家说的是在头尾的前后插入!!! 

疑问四:对于题解中的第三种情况是什么呢?

其实就是 

对于这四个疑问就全解答完毕了,如果有帮助,还请点赞。 


http://www.ppmy.cn/devtools/144072.html

相关文章

maven-resources-production:ratel-fast: java.lang.IndexOutOfBoundsException

Maven生产环境中遇到java.lang.IndexOutOfBoundsException的问题&#xff0c;尝试了重启电脑、重启IDEA等常规方法无效&#xff0c;最终通过直接重建工程解决了问题。 Rebuild Project 再启动OK

protobuf: 通讯录2.0

直接先展示2.0代码 contacts.proto&#xff1a; syntax "proto3";package contacts;message People{string name 1;int32 age 2;//里面是电话的类型&#xff0c;当然&#xff0c;现在只有一个类型message Phone{string phone 1;}//repeated 表示重复 相当于定义…

优化Lua-cURL:减少网络请求延迟的实用方法

Lua-cURL作为一个轻量级的HTTP客户端库&#xff0c;它在Lua环境中提供了对cURL的封装&#xff0c;使得网络请求变得简单快捷。然而&#xff0c;网络请求延迟仍然是一个需要关注和解决的问题。本文将探讨如何通过优化Lua-cURL来减少网络请求延迟&#xff0c;并提供一些实用的代码…

基于Springboot人口老龄化社区服务与管理平台【附源码】

基于Springboot人口老龄化社区服务与管理平台 效果如下&#xff1a; 系统登陆页面 系统主页面 社区信息页面 社区文件页面 活动报名页面 走访任务管理页面 社区资讯页面 老人信息管理页面 研究背景 随着社会老龄化的加剧&#xff0c;老年人口比例逐渐增加&#xff0c;对老年…

Unity复刻胡闹厨房复盘 模块一 新输入系统订阅链与重绑定

本文仅作学习交流&#xff0c;不做任何商业用途 郑重感谢siki老师的汉化教程与代码猴的免费教程以及搬运烤肉的小伙伴 版本&#xff1a;Unity6 模板&#xff1a;3D 核心 渲染管线&#xff1a;URP ------------------------------…

《手写Mybatis渐进式源码实践》实践笔记(第六章 数据源池化技术的实现)

文章目录 第6章 数据源池化技术的实现背景技术背景享元模式享元模式的主要特点包括&#xff1a;享元模式的应用场景&#xff1a;享元模式的优点&#xff1a;享元模式的缺点&#xff1a; 池化方案工作原理优势实现方式常用连接池技术配置与调优 业务背景 目标设计实现工程代码类…

MFC 自定义网格控件

一、什么是 Custom Control&#xff1f; Custom Control&#xff08;自定义控件&#xff09; 是 MFC&#xff08;Microsoft Foundation Classes&#xff09;框架中提供的一种控件类型&#xff0c;用于实现自定义的外观和功能。当标准控件&#xff08;例如 CEdit、CButton、CLi…

子域提取工具,子域名收集神器,支持多种数据源和枚举选项,域名发现工具,可以为任何目标枚举海量的有效子域名,安全侦察工具,利用证书透明原则监控部署的新子域

子域提取工具&#xff0c;子域名收集神器&#xff0c;支持多种数据源和枚举选项&#xff0c;域名发现工具&#xff0c;可以为任何目标枚举海量的有效子域名&#xff0c;安全侦察工具&#xff0c;利用证书透明原则监控部署的新子域。 需要对目标域名的子域进行深入分析&#xff…