2011年计算机等级考试二级C++辅导实例编程(27)

会计考友

　最长上升子序列LIS算法实现　　最长上升子序列问题是各类信息学竞赛中的常见题型，也常常用来做介绍动态规划算法的引例，笔者接下来将会对POJ上出现过的这类题目做一个总结，并介绍解决LIS问题的两个常用算法(n^2)和(nlogn).
, S9 a- v6 ?+ n+ {  l0 A
　　问题描述:给出一个序列a1,a2,a3,a4,a5,a6,a7....an,求它的一个子序列(设为s1,s2,...sn)，使得这个子序列满足这样的性质，s1

会计考友

{　　m=0;
　　for(j=1;jm&&a[j]ans)
　　ans=dp;
　　}
　　return ans;
% W0 F( m& p" J# L% W+ D　　}
# s% c' E" {9 |6 }' R2 O　　算法2(nlogn):维护一个一维数组c，并且这个数组是动态扩展的，初始大小为1，c表示最长上升子序列长度是i的所有子串中末尾最小的那个数，根据这个数字，我们可以比较知道，只要当前考察的这个数比c大，那么当前这个数一定能通过c构成一个长度为i+1的上升子序列。当然我们希望在C数组中找一个尽量靠后的数字，这样我们得到的上升子串的长度最长，查找的时候使用二分搜索，这样时间复杂度便下降了。
& W6 d1 r. d  [/ }　　模板如下：
　　//最长上升子序列nlogn模板
　　//入口参数:数组名+数组长度，类型不限，结构体类型可以通过重载运算符实现
　　//数组下标从1号开始。
　　/**//////////////////////////BEGIN_TEMPLATE_BY_ABILITYTAO_ACM////////////////////////////
5 c* T. n) n1 L3 S8 |　　template
1 b$ V2 j& ^7 V5 }9 M* {　　int bsearch(T c[],int n,T a)
　　{
　　int l=1, r=n;

　　while(l

会计考友

　{　　int mid = (l+r)/2;
8 o# i% b  W8 x0 J
　　if( a > c[mid] && a &&= &&