最长递增子序列.docx
- 文档编号:16239773
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:11
- 大小:22.84KB
最长递增子序列.docx
《最长递增子序列.docx》由会员分享,可在线阅读,更多相关《最长递增子序列.docx(11页珍藏版)》请在冰点文库上搜索。
最长递增子序列
var
a,f{DP记录},p{后面的}:
array[1..1000]oflongint;
i,j,k,n:
longint;
begin
readln(n);
fori:
=1tondo
begin
read(a[i]);
f[i]:
=1;{预处理}
end;
fori:
=n-1downto1do
forj:
=ndowntoi+1do
if(a[i] thenbegin p[i]: =j; f[i]: =f[j]+1; end; k: =0; fori: =ndownto1do iff[i]>j thenbegin j: =f[i]; k: =i; end; writeln(j); whilek<>0do begin write(k,''); k: =p[k]; end; end. 最长上升子序列的nlog(n)算法 [2007-7-78: 26: 00|By: TINYWOLF] 听说程序是cqf大牛d^_^ 刚开始一看,以为a数组是用来保存元素的,呵呵, 特点1: 每次输入一个元素都要进行处理,以求维护好整个数组。 那为什么要维护要整个数组呢? 假设最长可以达到i,那么1 如果输入一个元素t,比最大的那个大,那好办if(t>a[c-1])a[c++]=t; 如果不是呢,那t要插进数组里面去,代替一个没有必要存在的元素,为什么说它没有必要呢? 比如 135678469 前面都是比较顺,所以一下子积累到了1356 78,接着来了一个4这个4要代替5,而且这样做一点都不影响最后的结果(只会变好不会变坏)因为如果后来再来一个5就可以代替6的位置了,哈哈,下来的工作就交给cqf大牛的程序了^_^ - 特点2: 二分那里,一来为了更快找到代替元素,而来要注意上下指针的改变不一样,要代替的是比自己刚好大那么一dd(最小)的那个。 #include #include intmain() { inta[40005],c,m,n,i,k,t; scanf("%d",&m); while(m-->0) { scanf("%d",&n); if(n==0){printf("0\n");continue;} for(i=0;i<=n+2;i++)a[i]=0; c=1; scanf("%d",&t); a[0]=t; for(k=1;k { scanf("%d",&t); if(t>a[c-1])a[c++]=t; else { intl=0,h=c-1,mid=(l+h)/2; while(l { if(a[mid] elseif(a[mid]>t)h=mid; mid=(l+h)/2; } a[mid]=t; } } printf("%d\n",c); } return0; } Zju 1986 Bridging Signals 阅读全文(89)|回复(3)|引用通告(0)|编辑 标签: 算法-冗余的代码 最长公共子序列问题: 给定两个序列 X={x1,x2,...,xm} Y={y1,y2,...,yn} 求X和Y的一个最长公共子序列 举例 X={a,b,c,b,d,a,b} Y={b,d,c,a,b,a} 最长公共子序列为 LSC={b,c,b,a} 分析: 最长公共子序列问题具有最优子结构性质 设 X={x1,...,xm} Y={y1,...,yn} 及它们的最长子序列 Z={z1,...,zk} 则 1、若xm=yn,则zk=xm=yn,且Z[k-1]是X[m-1]和Y[n-1]的最长公共子序列 2、若xm! =yn,且zk! =xm,则Z是X[m-1]和Y的最长公共子序列 3、若xm! =yn,且zk! =yn,则Z是Y[n-1]和X的最长公共子序列 由性质导出子问题的递归结构 当i=0,j=0时, c[i][j]=0 当i,j>0;xi=yi时, c[i][j]=c[i-1][j-1]+1 当i,j>0;xi! =yi时,c[i][j]=max{c[i][j-1],c[i-1][j]} //////////////////////////////////////// 这种分析方法我总得比较有用,值得保存,所以就从book ----《计算机机算法设计与分析》电子工业出版社 中摘录出来,如果不明白,可以看一看原作。 //////////////////////////////////////// //书中只有关键部分的代码,现在已经补全 //源程序 #include"iostream.h" #include"iomanip.h" #definemax100 voidLCSLength(intm,intn,char*x,char*y,char*b) { inti,j,k; intc[max][max]; for(i=1;i<=m;i++) { c[i][0]=0; } for(i=1;i<=n;i++) { c[0][i]=0; } for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if(x[i-1]==y[j-1]) { c[i][j]=c[i-1][j-1]+1; k=i*(n+1)+j; b[k]='\\'; } elseif(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; k=i*(n+1)+j; b[k]='|'; } else { c[i][j]=c[i][j-1]; k=i*(n+1)+j; b[k]='-'; } } } } voidLCS(inti,intj,char*x,char*b,intwidth) { if(i==0||j==0) return; intk=i*(width+1)+j; if(b[k]=='\\') { LCS(i-1,j-1,x,b,width); cout< } elseif(b[k]=='|') { LCS(i-1,j,x,b,width); } else { LCS(i,j-1,x,b,width); } } voidmain() { charx[max]={'a','b','c','b','d','a','b'}; chary[max]={'b','d','c','a','b','a'}; intm=7; intn=6; charb[max]={0}; LCSLength(m,n,x,y,b); LCS(m,n,x,b,n); cout< } //////////////////////////////////////// 参考资料: 最长公共子序列问题LCS 问题描述 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 确切地说,若给定序列X= 例如,序列Z=是序列X=的子序列,相应的递增下标序列为<2,3,5,7>。 给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。 例如,若X=和Y=,则序列是X和Y的一个公共子序列,序列也是X和Y的一个公共子序列。 而且,后者是X和Y的一个最长公共子序列,因为X和Y没有长度大于4的公共子序列。 最长公共子序列(LCS)问题: 给定两个序列X= 参考解答 动态规划算法可有效地解此问题。 下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法。 1.最长公共子序列的结构 解最长公共子序列问题时最容易想到的算法是穷举搜索法,即对X的每一个子序列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列,并且在检查过程中选出最长的公共子序列。 X的所有子序列都检查过后即可求出X和Y的最长公共子序列。 X的一个子序列相应于下标序列{1,2,…,m}的一个子序列,因此,X共有2m个不同子序列,从而穷举搜索法需要指数时间。 事实上,最长公共子序列问题也有最优子结构性质,因为我们有如下定理: 定理: LCS的最优子结构性质 设序列X= 1.若xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列; 2.若xm≠yn且zk≠xm,则Z是Xm-1和Y的最长公共子序列; 3.若xm≠yn且zk≠yn,则Z是X和Yn-1的最长公共子序列。 其中Xm-1= 证明 1.用反证法。 若zk≠xm,则 这与Z是X和Y的一个最长公共子序列矛盾。 因此,必有zk=xm=yn。 由此可知Zk-1是Xm-1和Yn-1的一个长度为k-1的公共子序列。 若Xm-1和Yn-1有一个长度大于k-1的公共子序列W,则将xm加在其尾部将产生X和Y的一个长度大于k的公共子序列。 此为矛盾。 故Zk-1是Xm-1和Yn-1的一个最长公共子序列。 2.由于zk≠xm,Z是Xm-1和Y的一个公共子序列。 若Xm-1和Y有一个长度大于k的公共子序列W,则W也是X和Y的一个长度大于k的公共子序列。 这与Z是X和Y的一个最长公共子序列矛盾。 由此即知Z是Xm-1和Y的一个最长公共子序列。 3.与2.类似。 这个定理告诉我们,两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。 因此,最长公共子序列问题具有最优子结构性质。 2.子问题的递归结构 由最长公共子序列问题的最优子结构性质可知,要找出X= 当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。 当xm≠yn时,必须解两个子问题,即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。 这两个公共子序列中较长者即为X和Y的一个最长公共子序列。 由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。 例如,在计算X和Y的最长公共子序列时,可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。 而这两个子问题都包含一个公共子问题,即计算Xm-1和Yn-1的最长公共子序列。 与矩阵连乘积最优计算次序问题类似,我们来建立子问题的最优值的递归关系。 用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。 其中Xi= 当i=0或j=0时,空序列是Xi和Yj的最长公共子序列,故c[i,j]=0。 其他情况下,由定理可建立递归关系如下: 3.计算最优值 直接利用(2.2)式容易写出一个计算c[i,j]的递归算法,但其计算时间是随输入长度指数增长的。 由于在所考虑的子问题空间中,总共只有θ(m*n)个不同的子问题,因此,用动态规划算法自底向上地计算最优值能提高算法的效率。 计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X= 输出两个数组c[0..m,0..n]和b[1..m,1..n]。 其中c[i,j]存储Xi与Yj的最长公共子序列的长度,b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的,这在构造最长公共子序列时要用到。 最后,X和Y的最长公共子序列的长度记录于c[m,n]中。 ProcedureLCS_LENGTH(X,Y); begin m: =length[X]; n: =length[Y]; fori: =1tomdoc[i,j]: =0; forj: =1tondoc[0,j]: =0; fori: =1tomdo forj: =1tondo ifx[i]=y[j]then begin c[i,j]: =c[i-1,j-1]+1; b[i,j]: ="↖"; end elseifc[i-1,j]≥c[i,j-1]then begin c[i,j]: =c[i-1,j]; b[i,j]: ="↑"; end else begin c[i,j]: =c[i,j-1]; b[i,j]: ="←" end; return(c,b); end; 由于每个数组单元的计算耗费Ο (1)时间,算法LCS_LENGTH耗时Ο(mn)。 4.构造最长公共子序列 由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X= 首先从b[m,n]开始,沿着其中的箭头所指的方向在数组b中搜索。 当b[i,j]中遇到"↖"时,表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列;当b[i,j]中遇到"↑"时,表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同;当b[i,j]中遇到"←"时,表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。 下面的算法LCS(b,X,i,j)实现根据b的内容打印出Xi与Yj的最长公共子序列。 通过算法的调用LCS(b,X,length[X],length[Y]),便可打印出序列X和Y的最长公共子序列。 ProcedureLCS(b,X,i,j); begin ifi=0orj=0thenreturn; ifb[i,j]="↖"then begin LCS(b,X,i-1,j-1); print(x[i]);{打印x[i]} end elseifb[i,j]="↑"thenLCS(b,X,i-1,j)elseLCS(b,X,i,j-1); end; 在算法LCS中,每一次的递归调用使i或j减1,因此算法的计算时间为O(m+n)。 例如,设所给的两个序列为X=和Y=。 由算法LCS_LENGTH和LCS计算出的结果如图2所示。 j 0 1 2 3 4 5 6 i yj B D C A B A ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ 0 xi │ 0 0 0 0 0 0 │ │ ↑ ↑ ↑ ↖ ↖ │ 1 A │ 0 0 0 0 1 ← 1 1 │ │ ↖ ↑ ↖ │ 2 B │ 0 1 ← 1 ← 1 1 2 ← 2 │ │ ↑ ↑ ↖ ↑ ↑ │ 3 C │ 0 1 1 2 ← 2 2 2 │ │ ↖ ↑ ↑ ↑ ↖ │ 4 B │ 0 1 1 2 2 3 ← 3 │ │ ↑ ↖ ↑ ↑ ↑ ↑ │ 5 D │ 0 1 2 2 2 3 3 │ │ ↑ ↑ ↑ ↖ ↑ ↖ │ 6 A │ 0 1 2 2 3 3 4 │ │ ↖ ↑ ↑ ↑ ↖ ↑ │ 7 B │ 0 1 2 2 3 4 5 │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ 图2 算法LCS的计算结果 5.算法的改进 对于一个具体问题,按照一般的算法设计策略设计出的算法,往往在算法的时间和空间需求上还可以改进。 这种改进,通常是利用具体问题的一些特殊性。 例如,在算法LCS_LENGTH和LCS中,可进一步将数组b省去。 事实上,数组元素c[i,j]的值仅由c[i-1,j-1],c[i-1,j]和c[i,j-1]三个值之一确定,而数组元素b[i,j]也只是用来指示c[i,j]究竟由哪个值确定。 因此,在算法LCS中,我们可以不借助于数组b而借助于数组c本身临时判断c[i,j]的值是由c[i-1,j-1],c[i-1,j]和c[i,j-1]中哪一个数值元素所确定,代价是Ο (1)时间。 既然b对于算法LCS不是必要的,那么算法LCS_LENGTH便不必保存它。 这一来,可节省θ(mn)的空间,而LCS_LENGTH和LCS所需要的时间分别仍然是Ο(mn)和Ο(m+n)。 不过,由于数组c仍需要Ο(mn)的空间,因此这里所作的改进,只是在空间复杂性的常数因子上的改进。 另外,如果只需要计算最长公共子序列的长度,则算法的空间需求还可大大减少。 事实上,在计算c[i,j]时,只用到数组c的第i行和第i-1行。 因此,只要用2行的数组空间就可以计算出最长公共子序列的长度。 更进一步的分析还可将空间需求减至min(m,n)。 swordon|阅读全文(32)|回复(0)|反映问题|引用通告(0)|编辑 标签: 最长公共子序列问题LCS ∙上一篇: zoj1986 nlogn的最长子序列算法(转) ∙下一篇: zoj1025 贪心 查看所有评论
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最长 递增 序列
![提示](https://static.bingdoc.com/images/bang_tan.gif)