UVA - 10635 - Prince and Princess - （LCS最长公共子序列O（n*log(n）），LIS）

题目链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1576

题意：给出两个长度分别为p+1，q+1的数字序列，序列中数字范围为1~n*n，序列中数字不重复，让求序列的最大公共子序列。

解析：这里要用到O（n*log(n））的LIS最长上升子序列来求，具体步骤如下：

①.设有序列A，B，记序列A中各个元素在B 中的位置(记录时降序排列)；

②.将A中的“每个元素”替换为“该元素在B 中的位置集合(记录时降序排列)”；

③.然后求变化后的A的最长递增子序列。

例如：有A={a,b,a,c,x}，B={b,a,a,b,c,a}则有a={6,3,2},b={4,1},c={5};x=/;（注意降序排列）

然后按A中次序排出{a(6,3,2),b(4,1),a(6,3,2),c(5),x()}={6,3,2,4,1,6,3,2,5}；对此序列求最长递增子序列即可。

将求出来的最长上升子序列每个元素作为下标，对应到变化前的A中的可得到一个序列，即A与B的最长公共子序列。

其正确性的必要条件：

①.由于变化后的A集合与变化后前A集合元素是一一对应的，所以可以保证选出的最长上升子序列对于变化前A中的元素是遵循排列顺序的。

②.由于选出的元素的本质是B中某元素的下标，由于所选序列上升的，所以可以保证选出的最长上升子序列对于B的元素是遵循排列顺序的。

③.选出的元素一定即在A中又在B中，即是A与B的公共元素

④.LIS与LCS中两个最长相对应，保证结果是最长的。

注：这里求A中元素在B 中的位置集合时要降序排列能使得同一元素只选一次

以上是网上看到的LIS转LCS解释但是没有看到具体的代码。。。

下面的代码是另一种方式：

设A={a1,a2,a3...ap,ap+1}，将每个元素ai用mark[ai]记录其下标i；

设B={b1,b2,b3...bq,bq+1},生成数组ans[1]~ans[q+1]，其中ans[i]=mark[b[i]]

然后求ans数组的的最长递增子序列就行了

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 250*250+10;

int ans,n,p,q;
int a[M],b[M];
int mark[M],dp[M];
int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        memset(mark,0,sizeof(mark));

        scanf("%d%d%d",&n,&p,&q);
        for(int i=1;i<=p+1;i++)
        {
            scanf("%d",&a[i]);
            mark[a[i]]=i;
        }

        for(int i=1;i<=q+1;i++)
        {
            scanf("%d",&n);
            b[i]=mark[n];
            dp[i]=0;
        }

        int cnt=0;ans=1;
        for(int i=1;i<=q+1;i++)
        {
            int k=lower_bound(dp,dp+cnt,b[i])-dp;
            dp[k]=b[i];
            if(k==cnt) cnt++;
            ans=max(cnt,ans);
        }
        printf("Case %d: %d\n",++cas,ans);
    }
    return 0;
}
           

参考：

LIS原理：https://blog.csdn.net/accelerator_/article/details/11339459

http://blog.51cto.com/karsbin/966387

https://blog.csdn.net/tengfei461807914/article/details/51031355