UVa 497 Strategic Defense Initiative

题目描述题目要求从按到达顺序排列的导弹高度序列中找出最长严格递增子序列LISLongest Increasing Subsequence\texttt{LISLongest Increasing Subsequence}LISLongest Increasing Subsequence并输出子序列的长度和该子序列本身。题目保证解唯一。输入格式第一行一个整数TTT表示测试用例的数量后面跟一个空行。每个测试用例包含若干行每行一个整数导弹高度以空行结束。两个连续测试用例之间由一个空行分隔。输出格式对于每个测试用例输出一行Max hits: X其中XXX为最长子序列的长度然后输出该子序列中的每个高度每行一个。两个连续测试用例的输出之间由一个空行分隔。样例输入1 1 6 2 3 5输出Max hits: 4 1 2 3 5题目分析本题的核心是求解最长严格递增子序列并输出子序列本身。由于题目保证解唯一可以直接使用经典的O(nlog⁡n)O(n \log n)O(nlogn)贪心加二分算法并记录前驱信息。算法使用数组mmm记录每个长度的最小末尾值。使用数组indexer\textit{indexer}indexer记录每个长度对应的末尾元素在原序列中的索引。使用数组parent\textit{parent}parent记录每个元素在其最长子序列中的前驱索引。遍历每个元素xxx若xxx大于mmm的最后一个元素则追加到mmm末尾记录前驱。否则在mmm中找到第一个大于等于xxx的位置替换为xxx并更新前驱信息。最终indexer\textit{indexer}indexer的最后一个元素即为最长子序列最后一个元素的索引通过parent\textit{parent}parent回溯得到整个子序列。复杂度分析时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)空间复杂度O(n)O(n)O(n)。代码实现// Strategic Defense Initiative// UVa ID: 497// Verdict: Accepted// Submission Date: 2016-07-16// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorintnumbers,parent,indexer;intlis(){parent.clear();indexer.clear();parent.resize(numbers.size());vectorintm;m.push_back(numbers.front());indexer.push_back(0);parent[0]-1;for(inti1;inumbers.size();i){if(numbers[i]m.back()){m.push_back(numbers[i]);parent[i]indexer.back();indexer.push_back(i);}else{intnlower_bound(m.begin(),m.end(),numbers[i])-m.begin();m[n]numbers[i];if(n0)parent[i]-1;elseparent[i]indexer[n-1];indexer[n]i;}}returnm.size();}voidfindPath(inti){if(parent[i]!-1)findPath(parent[i]);coutnumbers[i]\n;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcasesstoi(line);getline(cin,line);for(inti1;icases;i){if(i1)coutendl;numbers.clear();while(getline(cin,line),line.length()0)numbers.push_back(stoi(line));coutMax hits: lis()\n;findPath(indexer.back());}return0;}