问题分析本题是典型的最长非递增子序列Longest Non-Increasing Subsequence\texttt{Longest Non-Increasing Subsequence}Longest Non-Increasing Subsequence问题。题目描述了一个导弹拦截系统CATCHER\texttt{CATCHER}CATCHER它能够拦截后续导弹的条件是后续导弹的高度不高于上一次拦截的导弹高度。由于导弹按照时间顺序依次到来我们需要在给定的高度序列中找出最长的非递增子序列的长度。需要注意的是题目中的输入是以-1作为每个测试用例的结束标志而连续两个-1则表示输入结束。解题思路求解最长非递增子序列的长度有多种方法动态规划法定义dp[i]dp[i]dp[i]表示以第iii个导弹结尾的最长非递增子序列的长度状态转移方程为dp[i]max⁡(dp[j])1,其中 ji 且 heights[j]≥heights[i]dp[i] \max(dp[j]) 1, \quad \text{其中 } j i \text{ 且 } heights[j] \ge heights[i]dp[i]max(dp[j])1,其中ji且heights[j]≥heights[i]时间复杂度为O(n2)O(n^2)O(n2)nnn为导弹数量。二分查找优化法本题代码采用的方法由于我们只关心最长序列的长度可以使用一个数组m来维护当前最长非递增子序列的“尾部元素”。对于非递增子序列当遇到一个新元素时我们使用upper_bound找到第一个大于当前元素的位置因为我们要保持非递增所以新元素应该替换掉第一个比它大的元素然后进行替换。最后m的长度即为答案。需要注意的是在计算之前代码先将原序列反转然后使用upper_bound处理这实际上是在求解最长非递减子序列等价于原问题的最长非递增子序列。代码实现// Testing the CATCHER// UVa ID: 231// Verdict: Accepted// Submission Date: 2016-05-09// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorintheights;// 计算最长非递增子序列的长度intlis(){// 反转序列将非递增问题转换为非递减问题reverse(heights.begin(),heights.end());// m 维护当前最长非递减子序列的尾部元素vectorintm;m.push_back(heights.front());for(inti1;iheights.size();i)// 如果当前高度不小于尾部元素直接扩展if(heights[i]m.back())m.push_back(heights[i]);else{// 找到第一个大于 heights[i] 的位置并替换intnupper_bound(m.begin(),m.end(),heights[i])-m.begin();m[n]heights[i];}returnm.size();}intmain(){cin.tie(0);cin.sync_with_stdio(false);boolfirsttrue;intheight,cases0;// 读取每个测试用例以 -1 结束while(cinheight,height!-1){heights.clear();heights.push_back(height);// 读取同一测试用例的后续高度while(cinheight,height!-1)heights.push_back(height);// 输出空行分隔不同测试用例if(first)firstfalse;elsecoutendl;cases;coutTest #cases:endl;cout maximum possible interceptions: lis()endl;}return0;}总结本题本质上是一个经典的最长非递增子序列问题使用O(nlog⁡n)O(n \log n)O(nlogn)的二分查找优化方法可以在规定时间内完成计算。理解问题转化为最长非递增子序列是关键代码实现相对简单。