GESP6级C++考试语法知识（四十三、动态规划----线性DP（四、双调序列 LIS + LDS））
第二阶段第四课
🎵《动物王国合唱团——LIS + LDS 联手出击》
🌟一、故事开始：动物王国音乐节
1、在算法王国里，
一年一度的：
🎵动物王国音乐节🎵
开始啦！
2、今年，
国王要举办一个超级盛大的：
🦁动物大合唱
3、参加演出的动物有：
小兔🐰
小猫🐱
小狗🐶
小鹿🦌
小熊🐻
……
很多很多。
4、每只动物都有一个身高。
例如：
130 150 170 200 180 160 140国王提出一个奇怪要求：
5、🌟站队时要像一座小山！
什么意思？
（1）前面越来越高：
130 150 170 200（2）后面越来越矮：
200 180 160 140（3）整个队伍看起来：
200 / \ 170 180 / \ 150 160 / \ 130 140像一座山！
6、国王说：
🌟请选择尽量多的动物组成这样的队形！
7、今天，
我们来解决这个问题！
🌟二、什么叫合唱队形？
1、例如：
130 150 170 200 180 160 1402、先升高：
130 150 170 2003、再降低：
200 180 160 1404、这就是：
🎵合唱队形
5、数学名字叫：
🌟双调序列
(Bi-tonic Sequence)
🌟三、这题为什么难？
1、上一课我们学了：
🚂LIS
最长上升子序列
2、例如：
1 3 2 4 5LIS：
1 2 4 5长度：
43、现在国王要求：
不仅要上升
还要下降
于是：
一个LIS不够用了！
4、🌟需要两个DP一起干活！
🌟四、第一个DP：LIS
1、我们先求：
up[i]表示：
2、以第i个人结尾
最长上升序列长度
（1）例如：
130 150 170 200 180 160 140（2）来到：
200（3）可以形成：
130 150 170 200（4）长度：
4（5）所以：
up[4] = 4;🌟五、第二个DP：LDS
1、什么叫LDS？
Longest Decreasing Subsequence
最长下降子序列
2、我们定义：
down[i]表示：
3、从第i个人开始
往右走到最后的
最长下降序列长度
4、例如：
200 180 160 140长度：
4所以：
down[4] = 4;5、同学们发现规律：
如果从最右侧向左一直推到i，计算down[i]
与我们从左侧到i的LIS算法是相同的！
🌟六、为什么要两个数组？
1、因为：
山峰左边：
需要上升。
山峰右边：
需要下降。
2、例如：
130 150 170 200 180 160 1403、山顶：
200（1）左边：
130 150 170 200长度：
4（2）右边：
200 180 160 140长度：
4（3）所以：
以200为山顶的数列长度为4+4-1 =7！
🌟七、山顶公式来了！
1、假设：
第i个人是山顶。
2、左边长度：
up[i]3、右边长度：
down[i]4、那么：
整个合唱队序列长度：
up[i] + down[i] - 15、为什么减1？
（1）因为：
山顶被数了两次！
（2）例如：
130 150 170 200有200
200 180 160 140也有200
（3）所以：
需要减掉一次。
🌟八、手工推例子
1、身高：
130 150 170 200 180 160 1402、先求：
up[]| 位置 | 130 | 150 | 170 | 200 | 180 | 160 | 140 |
|---|---|---|---|---|---|---|---|
| up | 1 | 2 | 3 | 4 | 4 | 3 | 2 |
3、再求：
down[]从右往左推：
| 位置 | 130 | 150 | 170 | 200 | 180 | 160 | 140 |
|---|---|---|---|---|---|---|---|
| down | 1 | 2 | 3 | 4 | 3 | 2 | 1 |
🌟九、作为山顶合起来
1、计算：
up[i]+down[i]-1| 位置 | up | down | 总长度 |
|---|---|---|---|
| 130 | 1 | 1 | 1 |
| 150 | 2 | 2 | 3 |
| 170 | 3 | 3 | 5 |
| 200 | 4 | 4 | 7 |
| 180 | 4 | 3 | 6 |
| 160 | 3 | 2 | 4 |
| 140 | 2 | 1 | 2 |
2、最大：
73、答案：
7整个队伍都能参加！
🌟十、不是所有人都能参加：
例如：
186 186 150 200 160 130 197 220我们要找：
最长山形队伍
🌟十一、参考代码
#include <iostream> using namespace std; int a[1005]; int up[1005]; int down[1005]; int main() { int n; cin >> n; for(int i=1;i<=n;i++) { cin >> a[i]; } // LIS for(int i=1;i<=n;i++) { up[i]=1; for(int j=1;j<i;j++) { if(a[j] < a[i]) { up[i]=max(up[i], up[j]+1); } } } // LDS for(int i=n;i>=1;i--) { down[i]=1; for(int j=n;j>i;j--) { if(a[j] < a[i]) { down[i]=max(down[i], down[j]+1); } } } int ans=0; for(int i=1;i<=n;i++) { ans=max(ans, up[i]+down[i]-1); } cout<<ans; return 0; }🌟十二、程序模拟
1、输入：
7 130 150 170 200 180 160 1402、最终：
ans = 73、输出：
7🌟十三、真正理解两个DP的配合
很多同学学到这里会发现：
LIS负责：
↗往上爬山。
LDS负责：
↘往下下山。
而：
up[i]+down[i]-1表示：
🌟如果第i个人当山顶
整个山有多大
这是本题的灵魂！
🌟十四、课堂挑战
🎯挑战1
求LIS：
1 2 3 4 5答案是多少？
🎯挑战2
求LDS：
5 4 3 2 1答案是多少？
🎯挑战3
自己手算：
1 3 5 4 2的：
up[] down[]🎯挑战4
如果要求：
最少删掉多少人
才能变成合唱队形？
提示：
总人数 - 最长合唱队形长度🌟十五、本课总结
✅ LIS
求上升长度
✅ LDS
求下降长度
✅ up[i]
以i结尾的最长上升序列
✅ down[i]
从i开始的最长下降序列
✅ 山顶公式
对于每个位置 i：
up[i]+down[i]-1
✅ 最终答案
所有山顶中的最大值
🌟下节课预告
下一课：
⚔️《数字迷宫——最大路径和》⚔️
我们将进入：
🚀二维动态规划进阶篇
学习如何在数字地图中寻找：
🌟价值最大的路线！
这也是很多经典题目的原型。