当前位置：首页 > news >正文

GESP6级C++考试语法知识（四十三、动态规划----线性DP（四、双调序列 LIS + LDS））

news 2026/6/1 9:58:30

第二阶段第四课

🎵《动物王国合唱团——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 140

2、先升高：

130 150 170 200

3、再降低：

200 180 160 140

4、这就是：

🎵合唱队形

5、数学名字叫：

🌟双调序列

(Bi-tonic Sequence)

🌟三、这题为什么难？

1、上一课我们学了：

🚂LIS

最长上升子序列

2、例如：

1 3 2 4 5

LIS：

1 2 4 5

长度：

3、现在国王要求：

不仅要上升

还要下降

于是：

一个LIS不够用了！

4、🌟需要两个DP一起干活！

🌟四、第一个DP：LIS

1、我们先求：

up[i]

表示：

2、以第i个人结尾

最长上升序列长度

（1）例如：

130 150 170 200 180 160 140

（2）来到：

（3）可以形成：

130 150 170 200

（4）长度：

（5）所以：

up[4] = 4;

🌟五、第二个DP：LDS

1、什么叫LDS？

Longest Decreasing Subsequence

最长下降子序列

2、我们定义：

down[i]

表示：

3、从第i个人开始

往右走到最后的

最长下降序列长度

4、例如：

200 180 160 140

长度：

所以：

down[4] = 4;

5、同学们发现规律：

如果从最右侧向左一直推到i，计算down[i]

与我们从左侧到i的LIS算法是相同的！

🌟六、为什么要两个数组？

1、因为：

山峰左边：
需要上升。

山峰右边：
需要下降。

2、例如：

130 150 170 200 180 160 140

3、山顶：

（1）左边：

130 150 170 200

长度：

（2）右边：

200 180 160 140

长度：

（3）所以：

以200为山顶的数列长度为4+4-1 =7！

🌟七、山顶公式来了！

1、假设：

第i个人是山顶。

2、左边长度：

up[i]

3、右边长度：

down[i]

4、那么：

整个合唱队序列长度：

up[i] + down[i] - 1

5、为什么减1？

（1）因为：

山顶被数了两次！

（2）例如：

130 150 170 200

有200

200 180 160 140

也有200

（3）所以：

需要减掉一次。

🌟八、手工推例子

1、身高：

130 150 170 200 180 160 140

2、先求：

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、最大：

3、答案：

整个队伍都能参加！

🌟十、不是所有人都能参加：

例如：

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; }