Pascal最长公共子序列问题.pptVIP

两个模型,最长上升子列问题LIS； 最长公共子序列问题 ；,最长上升子列问题LIS,问题： 给出一个数列，要求从这个数列中找出一个最长的子列，使得这个子列的元素是严格单调上升的。 输入： 第一行是一个数N，表示数列的长度。第二行是N个数，表示这个数列。其中N=300000。 输出： 输出仅有一个数，最长子列的长度。 样例输入： 6 3 7 2 4 6 8 样例输出： 4,分析:,1.考虑某个位,到达该位的最长上升序列只与其前面位的数字有关而与其后面位无关,即具有子结构性质; 2.设FI表示第I位数字的最长上升子序列长度,则FI值只与当AJAI(JI)对应的子序列有关,容易获得: FI=MAXFJ(AJAI(JI)+1 3.自底向上的方式计算问题的最优值,显然FI的初值为1,以下是对样例的模拟操作分析,设ai为第i个数，fi为到第i个数最长上升子序列的大小，初始时fi=0，f1=1，,procedure main; var i,j,max:integer; begin max:=1; f1:=1; for i:=2 to n do begin for j:=1 to i-1 do求符合条件子列最大值 if (ajfi) then fi:=fj; inc(fi);子列最大值加1 if fimax then max:=fi; end; writeln(max); end;,算法效率：O(n2),注意观察相同上升长度的子序列，如：长度为4的序列：3 5 6 8，3 4 5 7，3 4 5 6，影响后面最长子序列的是3 4 5 6序列。 证明： 因为6是长度为4序列中尾数最小的序列，如果一个数能加入长度为4的其它序列中也必定能加入该序列中。 故相同长度的子序列的有效信息是其序列中尾数最小的数。因此我们如果增加一个数组记录下每种序列结尾最小值，可不可以降低算法的时间复杂度呢？,序列 3 7 5 4 6 8 5 7 6 7 上升长度 1 2 2 2 3 4 3 4 4 5,建立一个数组sk来储存所有长度为j的最长上升子序列的最后一个数字的最小值。即,sk=minaJ( FJ=K,1=J=I)。,对sk能发现什么性质?,sK值是单调上升的!,改进算法: 原算法的弊端是每次需要花O(n)的时间寻找最优子序列. 由于sK值是单调上升 (1)考虑到ai元素时，用二分法在sk中寻找最大的一个k使skaI，让fI=k+1,否则fI保留原值. (2)IF AI SfI THEN 更新SfI=AI 这样，使算法的复杂度下降为O(nlog2n)。,分步变化示例如下:,(1),(2),(3),(4),(5),(6),program LIS; var n,i,max,k,e:integer;n数据长度，e记录已知序列总数，max最优值 num,dp,maxn:array 1300000 of integer;num记录数据，dp记录序列长度，maxn记录每种序列结尾最小值 function find(x:integer):integer;二分查找，寻找当前值所在的区间 var left,right,mid:integer; begin left:=1;right:=e; mid:=(left+right) div 2; while leftx then right:=mid-1 else left:=mid+1; mid:=(left+right) div 2; end; find:=mid-1; end;,begin assign(input,lis.in); reset(input); assign(output,lis.out); rewrite(output); readln(n); for i:=1 to n do maxni:=30000; for i:=1 to n do read(numi); dp1:=1; maxn1:=num1; e:=1; for i:=2 to n do 动态规划过程 begin k:=find(numi)+1; if k+1dpi then dpi:=k+1; if k+1e then e:=k+1; if numimaxndpi then maxndpi:=numi; end;,max:=0; for i:=1 to n do if maxdpi then max:=dpi; writeln(max); close(output); end.,【问题】 求两字符序列的最长公共字符子序列,问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，xm-1”，序列Y=“y0，y1，yk-1”是X的子序列，存在X的一个严格递增下标序列，使得对所有的j=0，1，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。,考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，am-1”，B=“b0，b1，bm-1”，并Z=“z0，z1，zk-1”为它们的最长公共子序列。不难证明有以下性质： （1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，zk-2”是“a0，a1，am-2”和“b0，b1，bn-2”的一个最长公共子序列； （2） 如果am-1bn-1，则若zk-1am-1，蕴涵“z0，z1，zk-1”是“a0，a1，am-2”和“b0，b1，bn-1”的一个最长公共子序列； （3） 如果am-1bn-1，则若zk-1bn-1，蕴涵“z0，z1，zk-1”是“a0，a1，am-1”和“b0，b1，bn-2”的一个最长公共子序列。 这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，am-2”和“b0，b1，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，am-2”和“b0，b1，bn-1”的一个最长公共子序列和找出“a0，a1，am-1”和“b0，b1，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。,求解：引进一个二维数组c，用cij记录Xi与Yj 的LCS 的长度，bij记录cij是通过哪一个子问题的值求得