当前位置:首页 > 最长子序列

牛客网4456题 最长递增子序列:动态规划+二分查找

1个月前 (07-31)367
牛客网4456题 最长递增子序列:动态规划+二分查找
本文深入解析牛客网4456题的经典解法,通过结合动态规划与二分查找,将最长上升子序列(LIS)问题的时间复杂度优化至O(nlogn)。文章详细拆解算法步骤,以[2,1,4,3,1,5,6]为例演示维护动态数组的核心逻辑,阐明为何替换操作不影响结果正确性,并对比传统O(n²)方法的差异。最后提供复杂度...

1999年NOIP提高组导弹拦截(洛谷P1020):从暴力到最优解

2个月前 (07-08)123
1999年NOIP提高组导弹拦截(洛谷P1020):从暴力到最优解
本文详细解析1999年NOIP提高组经典题目导弹拦截(洛谷P1020)的解题思路。通过分析题目要求的两个关键问题:计算单套系统最多拦截导弹数(最长不上升子序列)和拦截所有导弹所需最少系统数(最长上升子序列),展示了从暴力解法到O(nlogn)最优解法的完整优化过程。文章包含完整代码实现,配有详细注释...