[蓝桥杯 2019 国 B] 分列数

目次

媒介
题解
思绪
疑问
解答

---

媒介

对于本篇文章是站在别人的根本之上来写的，对于这道题作为2019年国赛B组的最难的一题，他的难度肯定是不小的，这道题我再一开始打仗的时间连思绪都没有，也是看了两三遍别人发的题解，才渐渐明白了怎么去写。那么对于题解我就直接引用别人的精良题解，但后再加上我对题解写的不详细的地方举行尽大概详细的形貌增补。
题解

以下题解全来自洛谷
思绪

设状态 dp[j]dp[j] 此中 ii 体现前 ii 个数中，有 jj 个折点的方案数。
思量状态转移，显然 dp[j]dp[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 是全部数中最大的，以是只要在非头/尾部插入这个点，这个点肯定就是新的折点。

• 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 才气满意不增长新折点）。
  
  
  
  
• dp[i+1][j+1]dp[i+1][j+1] 体现插入第 i+1个点后新增了一个迁徙变化点。
  只有一种情况，即当在序列头和尾向下走时在头和尾前后插入 i+1只增长一个迁徙变化点，如图，xx 为新增的一个迁徙变化点。
  
  
  
  
  以是转移方程：
  dp[i+1][j+1]=dp[j]×2dp[i+1][j+1]=dp[j]×2
  
• dp[i+1][j+2]dp[i+1][j+2] 体现插入第 i+1 个点后新增了两个迁徙变化点。
  显然在除了以上全部情况，其他地方插入 i+1i+1 都会新增两个折点，转移方程：
  

初始值：dp[1][0]=1dp[1][0]=1、dp[0]=2(1<i<n)dp[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呢？
   关于这个疑问，也是我疑惑时间最长的。
但想明白了实在照旧蛮简朴的，实在就是题解形貌的不敷清晰，
这个只是差别构型下会产生差别的效果，但是这个加的位置也就是题解里思量的范围，硬要说就是题解表述不完全，没有对全部构型画图。

留意：人家说的是在头尾的前后插入！！！ 
   疑问四：对于题解中的第三种情况是什么呢？
  实在就是 

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