题解 P1439 【【模板】最长公共子序列】

· · 题解

P1439 【模板】最长公共子序列 题解

适合下面没有读懂的OIer不适用于dalao。。

我打算写一发通俗易懂的题解。。 首先dp是n^2暴力算法显然只能拿50%的分数，我这里就贴下代码：

# include <iostream>
# include <cstring>
# include <cstdio>
using namespace std;
int a[5000],b[5000],f[5000][5000];
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) scanf("%d",&b[i]);
    for (int i=0;i<=n;i++)
     for (int j=0;j<=n;j++)
      {
        if ((i==0)||(j==0)) {
            f[i][j]=0;continue;
          }
        if (a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
        if (a[i]!=b[j]) f[i][j]=max(f[i][j-1],f[i-1][j]);
      }
      printf("%d\n",f[n][n]);
    return 0;
}

n^2暴力算法只能拿50分。。不满意。。

然而我们有一种优秀的 n log n 算法来解决这道LCS问题，就是单调队列优化，这是基于一个贪心。首先我们来考虑这样一个问题：

假设有t[]数组，求t[]的最长上升子序列。（LIS）

我们可以这么考虑（n^2就不用赘述了） 我们设一个单调递增的队列来存我们目前最优的LIS序列，什么是最优呢？ 包括数字最小、长度最大（这样才最有可能接受下一个比较小的数字变成更长的LIS），

那么问题就简单化了。具体来说如果有一个数组a是{4,5}（上述的单调队列a）我现在有一个数字3插入进去那么我只要把4改为3就行了（反正没有损失又使我们的数字小了）。

不巧的是后来有了个4来了，那么把5改为4（满足递增），这样a数组就变成了{3,4}那么相对于{4,5}有什么好处呢？

假设我们又来了数字5那么对于原来最优的{4,5}我的5是不满足最长上升子序列的，而对{3,4}来说5是可以加入拖长这个最优解LIS长度的，现在我们最优值变成{3,4,5}==>ans=3.

好了对于上述LIS问题我们有一个n log n的解法了：

设t[]为原数组，a[]为单调递增的最优解法队列，枚举n个元素如果t[i]>a[i]，直接吧t[i]加入a[i]；如果t[i]<a[i]在a[]中二分法（a有序！）找到一个比t[i]大的最小数，并将其替换为t[i]满足最优解法（虽然不是更优LIS解但是相比其他相同LIS长度解法它更有优势）

回到本题求LCS的长度，怎样把他转移到LIS问题呢？

我们设A,B分别为两个数组的值，那么我只要保存A的元素在B中的位置，B 中的元素在A中的位置不就可以解决了吗？

好，我设t[]表示A数组B[i]元素在A中的位置（序号），那么这个序号在B中出现本来就有先后位置，再保存A中的位置那么就可以表示出A的序列了。

举个例子。 序号 1 2 3 4 5 A[]=3 2 1 4 5 B[]=1 2 3 4 5 按照上述算法映射后t[]=3 2 1 4 5

那么很显然t中的数字如果递增

那么表示A中的序号递增就表示这个递增的序列就是A的子序列， 并且我们在B中一直的顺序遍历（从前向后）那么显然这个序列也是B的子序列， 那么这个序列就是A,B公共子序列，

那么最大化这个子序列就是最大化t数组中的最长上升子序列LIS算法，

这样我们就把LCS问题变成LIS问题用n log n解决了。

代码：

//tips：手写lower_bound比调用algorithm快一些。。

# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
int a[100005],t[100005],A[100005],B[100005],f[100005];
bool cmp(int a,int b)
{
    return a<b;
}
int solve(int l,int r,int x)
{
    int mid=(l+r)/2;;
    if (l==r) return l; 
    if (a[mid]>x) return solve(l,mid,x);
    if (a[mid]<=x) return solve(mid+1,r,x);
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&A[i]);
    for (int i=1;i<=n;i++) scanf("%d",&B[i]);
    for (int i=1;i<=n;i++) f[A[i]]=i;
    for (int i=1;i<=n;i++) t[i]=f[B[i]];
    memset(a,0,sizeof(a));
    for (int i=1;i<=n;i++) {
        if ((i==0)||(t[i]>a[a[0]])) a[++a[0]]=t[i];
        else if (t[i]<a[a[0]]) a[solve(1,a[0],t[i])]=t[i];
//a[lower_bound(a+1,a+a[0]+1,t[i])-a]=t[i];(替换a[solve(1,a[0],t[i])]=t[i];也行但是会稍微慢一点。。)
    }
    printf("%d\n",a[0]); 
    return 0;
}

我们可以扩展一下这个算法，把它扩展为普通字符串的最大LCS问题，采用map数组（最大长度MAXN，最多重复次数MAXT），算法大概是这样的：我们把a序列中的每个元素在b中出现的位置保存起来，再按照降序排列，排列后再代入a的每个对应元素，那就转化为了求这个新的序列的最长上升子序列了。如：a[] = {a, b, c,} b[] = {a,b,c,b,a,d},那么a中的a，b，c在b中出现的位置分别就是

{0,4},{1,3},{2}分别按降序排列后代入a序列就是{4,0,2,3,1},之所以要按照降序排列，目的就是为了让每个元素只取到一次。

接下来的问题就是要求最长升序子序列问题了，也就是求LIS。

但是有人认为这种转化并没有多大意义，因为当数据比较大时，举一个例子来说：a[]= “aaaaaaaaaaa”,b[] = "aaaaaaaaaaa",他们都有n个a，那么a[]中‘a’在b[]出现了n次那么替换之后的a就变为了n-1...1,n-1...1,... ...这样a[]就有了n^2个数了这样不仅是空间，就连时间也比原来n^2要大。所以感觉这种转化还是要慎用。

那么我还是贴一下代码吧： (我比较蒟蒻想不出更加高深的算法那么假装这个是kn log n算法了，常数k应该比较大。。。)

# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <map>
using namespace std;
const int MAXN=100000,MAXT=1000;
int a[MAXN+1],t[MAXN+1];
char A[MAXN+1],B[MAXN+1],T[MAXN+1];
int f[MAXN+1][MAXT+1];
int n,m;
map<char,int>key;
bool cmp(int a,int b)
{
    return a>b;
}
void copy(int cnt)
{
    for (int i=1;i<=f[cnt][0];i++)  
      t[++t[0]]=f[cnt][i];
}
void swap(int &a,int &b)
{
    int t=a;a=b;b=t;
}
void change()
{
    memcpy(T,A,sizeof(A));memcpy(A,B,sizeof(B));memcpy(B,T,sizeof(T));
}
int main()
{
    scanf("%d",&n);getchar();
    for (int i=1;i<=n;i++) scanf("%c",&A[i]);getchar();
    scanf("%d",&m);getchar();
    for (int i=1;i<=m;i++) scanf("%c",&B[i]);getchar();
    if (n>m) { change(); swap(n,m); }
    int tot=0;
    for (int i=1;i<=n;i++)  {
        if (key.count(A[i])==0) key[A[i]]=++tot;
        f[key[A[i]]][++f[key[A[i]]][0]]=i;
    }
    for (int i=1;i<=tot;i++)  sort(f[i]+1,f[i]+f[i][0]+1,cmp);      
    memset(t,0,sizeof(t));
    for (int i=1;i<=m;i++) {
        if (key.count(B[i])==0) continue;
        else  copy(key[B[i]]);
    }   
    memset(a,0,sizeof(a));
    for (int i=1;i<=t[0];i++) 
        if ((t[i]>a[a[0]])) a[++a[0]]=t[i];
        else if (t[i]<a[a[0]]) a[lower_bound(a+1,a+a[0]+1,t[i])-a]=t[i];
    printf("%d\n",a[0]); 
    return 0;
}