[蓝桥杯 2019 国 B] 排列数

目录

前言

题解

思路

疑问

解答

---

前言

对于本篇文章是站在别人的基础之上来写的，对于这道题作为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呢？

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

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

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

注意：人家说的是在头尾的前后插入！！！ 

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

其实就是 

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