注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

最长公共递增子序列(LCIS)  

2013-01-23 15:30:32|  分类: ACM-Steps |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
给出两个序列a和b,求序列的最长公共递增子序列
例如 a:1,4,2,5,-12   b:-12,1,2,4,最长的公共递增子序列是2(序列为2,4)。

解决方案:
用一个二维数组f[i][j]表示a序列的前i项,b序列的前j项,并且以b[j]结束的LCIS。
则有:
当a[i] != b[j]时,f[i][j]=f[i-1][j];
当a[i] == b[j]时,f[i][j]=max(f[i-1][k])+1,1<=k<=j-1 && b[j]>b[k];
但是这样的效率为O(n^3)。 不难发现,求f[i-1][k]的时候可以通过一个变量temp来解决,当k从1遍历到j的同时,可以不断更新temp的值,如果a[i]>b[j]时,令temp=max(temp,f[i-1][j]);如果a[i]==b[j]时,令f[i][j]=max+1。

#define N 1010
int a[N],b[N];
int f[N][N];

int LCIS(int a[],int b[],int lena,int lenb)
{
int i,j,temp;
memset(f,0,sizeof(f));
for(i=1;i<=lena;i++)
{
for(j=1,temp=0;j<=lenb;j++)
{
f[i][j]=f[i-1][j];
if(a[i]>b[j] && f[i-1][j]>temp)
temp=f[i-1][j];
if(a[i] == b[j])
f[i][j]=temp+1;
}
}
temp=0;
for(i=1;i<=lenb;i++)
if(f[lena][i] > temp)
temp=f[lena][i];
return temp;
}


f数组也可以改成一维数组,减少空间。f[i]表示原来的f[i][j],f[i]的值可以沿用上一次循环的值,所以原来代码中的f[i][j]=f[i-1][j]可以省略。

int f[N];
int LCIS(int a[],int b[],int lena,int lenb)
{
int i,j,temp;
for(i=1;i<=lena;i++)
{
for(j=1,temp=0;j<=lenb;j++)
{
if(a[i]>b[j] && f[j]>temp)
temp=f[j];
if(a[i]==b[j])
f[j]=temp+1;
}
}
temp=0;
for(i=1;i<=lenb;i++)
if(f[i]>temp)
temp=f[i];
return temp;
}


  评论这张
 
阅读(337)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018