云梦做网站的优势,用什么做网站开发,互联网装饰网站,美食网站建设总结目录 前言
题解
思路
疑问
解答 前言
对于本篇文章是站在别人的基础之上来写的#xff0c;对于这道题作为2019年国赛B组的最难的一题#xff0c;他的难度肯定是不小的#xff0c;这道题我再一开始接触的时候连思路都没有#xff0c;也是看了两三遍别人发的题解#x…目录 前言
题解
思路
疑问
解答 前言
对于本篇文章是站在别人的基础之上来写的对于这道题作为2019年国赛B组的最难的一题他的难度肯定是不小的这道题我再一开始接触的时候连思路都没有也是看了两三遍别人发的题解才慢慢明白了怎么去写。那么对于题解我就直接引用别人的优秀题解但后再加上我对题解写的不详细的地方进行尽可能详细的描述补充。
题解
以下题解全来自洛谷
思路
设状态 dp[i][j]dp[i][j] 其中 ii 表示前 ii 个数中有 jj 个折点的方案数。
考虑状态转移显然 dp[i][j]dp[i][j] 只能影响到 dp[i1][j]dp[i1][j]、dp[i1][j1]dp[i1][j1]、dp[i1][j2]dp[i1][j2]证明如下
首先需要确定在原序列中插入第 i1i1 个数这个 i1i1 是所有数中最大的所以只要在非头/尾部插入这个点这个点一定就是新的折点。 dp[i1][j]dp[i1][j] 表示插入第 i1i1 个点后没有新增折点 例 情况一如图当 i1i1 插入波峰 xx 左右侧时xx 不再是折点折点变成了 i1i1此时折点数不变。 情况二如图当 i1i1 插入序列头尾 xx 左右时xx 依然不是折点序列没有新增折点此时折点数不变如果头或尾的点是向下走的那么插入后新增了一个点不属于该范围此时只有在其中一边插入 i1i1 才能满足不增加新折点。 dp[i1][j1]dp[i1][j1] 表示插入第 i1个点后新增了一个转折点。 只有一种情况即当在序列头和尾向下走时在头和尾前后插入 i1只增加一个转折点如图xx 为新增的一个转折点。 所以转移方程 dp[i1][j1]dp[i][j]×2dp[i1][j1]dp[i][j]×2 dp[i1][j2]dp[i1][j2] 表示插入第 i1 个点后新增了两个转折点。 显然在除了以上所有情况其他地方插入 i1i1 都会新增两个折点转移方程
初始值dp[1][0]1dp[1][0]1、dp[i][0]2(1in)dp[i][0]2(1in)。
答案dp[n][k−1]dp[n][k−1]。
疑问
我问的疑问的地方就是我上面标红的地方以及图片插入的地方是由这些地方而引出的疑问。 1为什么只在波峰处的左右插入在峰谷处插入不符合为什么呢 2为什么第一种情况下的公式为什么奇数情况下是j-1/2偶数下是j/2 3插入第 i1 个点后新增了一个转折点这种情况按照如图所表示他应该是只由特殊情况下只会增加二啊为什么用公式总结下来是直接*2呢 就比如这种情况我也没在头尾处插入啊那他这种情况也是属于增加了一个转折点啊 4对于题解中的第三种情况是什么呢 解答
相信你看完上面的四个疑问心里肯定会有所疑问那也相信通过你自己的思考肯定会解决一两个疑问。无论如何下面就由我来为大家解决四个疑问。 疑问一 为什么只在波峰处的左右插入在峰谷处插入不符合为什么呢 其实这个疑问人家题解也说的很明确了也解释了在波峰处插入确实不会增加转折点但我还是要说一点这里人家只说是在波峰的左右处插入没有说在峰谷插入的问题这个一定要注意。而且在疑问三中我也用图解释了在峰谷处插入也确实是会增加一个转折点的。所以不增加转折点的插入方法就只有两种情况也就是题解说的两种情况。 疑问二 为什么第一种情况下的公式为什么奇数情况下是j-1/2偶数下是j/2 关于这个疑问我们首先要知道一个结论当转折点是奇数时转折点数峰谷波峰波峰*21/峰谷*21相差不超过1。这是因为在一个排列中波峰和峰谷是交替出现的。例如如果一个排列从一个波峰开始那么接下来可能是一个峰谷然后再是一个波峰
当转折点时偶数时峰谷波峰 这可以通过大量的举例来观察得到。我这里就简单的给大家简单的证明一下
首先我们假设他的头与尾都是朝上的情况大致如图所示 那么如果图中有一个波峰那么他一定是比他的左右都是大的图略有粗糙能看明白就行
假如这个波峰的高度是小于两边的高度的那他还是会至少存在两个峰谷的。
假如这个波峰的高度在两边高度之间那么同样因为存在一个波峰的原因他至少会存在两个峰谷。
假如这个波峰的高度高于两边的高度那么这时候会存在两种情况第一种情况是没有峰谷还有一种情况就是至少存在两个峰谷。 以次类推在讨论当两边的头尾是向下的情况 如果在中间插入一个波峰
然后再分三种情况与两边的高度做套路
假设他的高度高于两边那么峰谷的数量为0或者至少为两个
假设他的高度再二者中间那么必定还存在一个与之相对应的波峰还有中间存在一个峰谷。
假设他的高度再二者之下那么那么他必有一个向下的调整那么对于这种情况他必定会至少由三个波峰两个峰谷。 对于上面的解释说明肯定说的不是很清楚但是只要知道一点
当转折点是奇数时转折点数峰谷波峰波峰*21/峰谷*21相差不超过1。这是因为在一个排列中波峰和峰谷是交替出现的。例如如果一个排列从一个波峰开始那么接下来可能是一个峰谷然后再是一个波峰
当转折点时偶数时峰谷波峰 所以公式中也就是用 j-1/2 来计算的。 疑问三插入第 i1 个点后新增了一个转折点这种情况按照如图所表示他应该是只由特殊情况下只会增加二啊为什么用公式总结下来是直接*2呢 关于这个疑问也是我疑惑时间最长的。
但想明白了其实还是蛮简单的其实就是题解描述的不够清楚
这个只是不同构型下会产生不同的结果但是这个加的位置也就是题解里考虑的范围硬要说就是题解表述不完全没有对全部构型画图。 注意人家说的是在头尾的前后插入 疑问四对于题解中的第三种情况是什么呢 其实就是 对于这四个疑问就全解答完毕了如果有帮助还请点赞。
