uva10635(LCS转换为求LIS)

本文主要是介绍uva10635(LCS转换为求LIS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：点击打开链接

题意：求两个串的最长公共子序列(两个串长度最大为250*250)

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int a[100005],b[100005],dp[100005],pos[100005];
int main(){                                     //样例A={1,7,5,4,8,3,9},B={1,4,3,5,6,2,8,9}int t,n,p,q,i,j,cas;                        //因为A,B中，每个数字只出现一次,因此对A,B中的scanf("%d",&t);                             //数进行重新编号，编号后for(cas=1;cas<=t;cas++){                    //A={0,1,2,3,4,5,6},B={0,3,5,2,-1,-1,4,6}scanf("%d%d%d",&n,&p,&q);               //-1代表没出现过,因此就变成求数组B的LISmemset(dp,INF,sizeof(dp));              //因此就从O(n*n)的LCS转换成O(n*logn)的LISmemset(pos,-1,sizeof(pos));for(i=0;i<p+1;i++){scanf("%d",&a[i]);pos[a[i]]=i;}for(i=0;i<q+1;i++){scanf("%d",&b[i]);b[i]=pos[b[i]];}for(i=0;i<q+1;i++)*lower_bound(dp,dp+q+1,b[i])=b[i];printf("Case %d: %d\n",cas,lower_bound(dp,dp+q+1,INF)-dp);}return 0;
}

 

这篇关于uva10635(LCS转换为求LIS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---