第二阶段第四课《动物王国合唱团——LIS LDS 联手出击》一、故事开始动物王国音乐节1、在算法王国里一年一度的动物王国音乐节开始啦2、今年国王要举办一个超级盛大的动物大合唱3、参加演出的动物有小兔小猫小狗小鹿小熊……很多很多。4、每只动物都有一个身高。例如130 150 170 200 180 160 140国王提出一个奇怪要求5、站队时要像一座小山什么意思1前面越来越高130 150 170 2002后面越来越矮200 180 160 1403整个队伍看起来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 5LIS1 2 4 5长度43、现在国王要求不仅要上升还要下降于是一个LIS不够用了4、需要两个DP一起干活四、第一个DPLIS1、我们先求up[i]表示2、以第i个人结尾最长上升序列长度1例如130 150 170 200 180 160 1402来到2003可以形成130 150 170 2004长度45所以up[4] 4;五、第二个DPLDS1、什么叫LDSLongest 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、山顶2001左边130 150 170 200长度42右边200 180 160 140长度43所以以200为山顶的数列长度为44-1 7七、山顶公式来了1、假设第i个人是山顶。2、左边长度up[i]3、右边长度down[i]4、那么整个合唱队序列长度up[i] down[i] - 15、为什么减11因为山顶被数了两次2例如130 150 170 200有200200 180 160 140也有2003所以需要减掉一次。八、手工推例子1、身高130 150 170 200 180 160 1402、先求up[]位置130150170200180160140up12344323、再求down[]从右往左推位置130150170200180160140down1234321九、作为山顶合起来1、计算up[i]down[i]-1位置updown总长度1301111502231703352004471804361603241402122、最大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 i1;in;i) { cin a[i]; } // LIS for(int i1;in;i) { up[i]1; for(int j1;ji;j) { if(a[j] a[i]) { up[i]max(up[i], up[j]1); } } } // LDS for(int in;i1;i--) { down[i]1; for(int jn;ji;j--) { if(a[j] a[i]) { down[i]max(down[i], down[j]1); } } } int ans0; for(int i1;in;i) { ansmax(ans, up[i]down[i]-1); } coutans; return 0; }十二、程序模拟1、输入7 130 150 170 200 180 160 1402、最终ans 73、输出7十三、真正理解两个DP的配合很多同学学到这里会发现LIS负责↗往上爬山。LDS负责↘往下下山。而up[i]down[i]-1表示如果第i个人当山顶整个山有多大这是本题的灵魂十四、课堂挑战挑战1求LIS1 2 3 4 5答案是多少挑战2求LDS5 4 3 2 1答案是多少挑战3自己手算1 3 5 4 2的up[] down[]挑战4如果要求最少删掉多少人才能变成合唱队形提示总人数 - 最长合唱队形长度十五、本课总结✅ LIS求上升长度✅ LDS求下降长度✅ up[i]以i结尾的最长上升序列✅ down[i]从i开始的最长下降序列✅ 山顶公式对于每个位置 iup[i]down[i]-1✅ 最终答案所有山顶中的最大值下节课预告下一课⚔️《数字迷宫——最大路径和》⚔️我们将进入二维动态规划进阶篇学习如何在数字地图中寻找价值最大的路线这也是很多经典题目的原型。