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

会计考友 · 发表于 2012-7-31 21:56:58

　最长上升子序列LIS算法实现　　最长上升子序列问题是各类信息学竞赛中的常见题型，也常常用来做介绍动态规划算法的引例，笔者接下来将会对POJ上出现过的这类题目做一个总结，并介绍解决LIS问题的两个常用算法(n^2)和(nlogn).

　　问题描述:给出一个序列a1,a2,a3,a4,a5,a6,a7....an,求它的一个子序列(设为s1,s2,...sn)，使得这个子序列满足这样的性质，s1

会计考友 · 发表于 2012-7-31 21:56:59

{　　m=0;
　　for(j=1;jm&&a[j]ans)
　　ans=dp;
+ c; z( m4 j$ b6 B* Q: f　　}$ b7 }6 X$ l4 k
　　return ans;5 Y7 a- Z# Y$ S
　　}. v3 p: R, `! F2 b
　　算法2(nlogn):维护一个一维数组c，并且这个数组是动态扩展的，初始大小为1，c表示最长上升子序列长度是i的所有子串中末尾最小的那个数，根据这个数字，我们可以比较知道，只要当前考察的这个数比c大，那么当前这个数一定能通过c构成一个长度为i+1的上升子序列。当然我们希望在C数组中找一个尽量靠后的数字，这样我们得到的上升子串的长度最长，查找的时候使用二分搜索，这样时间复杂度便下降了。
0 h: L2 g( ]+ D$ t0 a( V　　模板如下：
. Z5 h7 t9 ^. t9 X8 ]( i% V4 e　　//最长上升子序列nlogn模板
- j. |! k: i0 K' l/ Z5 c" S　　//入口参数:数组名+数组长度，类型不限，结构体类型可以通过重载运算符实现) h: |; P, M# i8 b4 N5 N2 g
　　//数组下标从1号开始。) F: b( S7 C" |4 u" ?4 G
　　/**//////////////////////////BEGIN_TEMPLATE_BY_ABILITYTAO_ACM////////////////////////////2 G& e) \3 C- E8 v; F. u4 o
　　template# a0 L8 h: O7 |! P# [ g
　　int bsearch(T c[],int n,T a)
+ r6 U, b6 U1 K) q0 z　　{
& Q' }, C9 G$ m5 i+ [% R$ g1 Z　　int l=1, r=n;9 j2 j* ^3 g) g

. s8 F( X3 y0 M3 {1 O　　while(l

会计考友 · 发表于 2012-7-31 21:57:00

　{　　int mid = (l+r)/2;

　　if( a > c[mid] && a &&= &&

		自动登录	找回密码
密码			立即注册

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

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

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