uva10635Prince and Princess(LIS)

Dear 丶 2021-12-17 03:17 236阅读 0赞

## 题意：求最长相同公共子序列。 ##

## 分析：《训练指南》P66，本题是一道经典的题目，巧妙的将LCS问题转化为LIS问题。这种题目的一个特定就是其中一个序列的所有元素均不相同。首先，我们可以对A数组重新编号为\{1,2,3,...n\}，接下来对于B数组的每个元素，替换为A中那个元素的编号，若没有在A中出现，那么直接置0，这样，B数组也变为一个由编号构成的数组，此时我们发现，A数组是一个自然序列，那么只要在B中找到最长上升的子序列，就是和A的最长公共子序列！这就是本题的巧妙之处！而LIS问题有O(N\*logN)的解法，因此可以通过本题的数据规模。 ##

## 为什么呢？ ##

## A'中为A中元素的代号 即 它们的顺序号 ##

## B'中为B中元素对应的代号（为了分析方便，这里将B中有而A中没有出现的去掉，等价于置0） ##

## 因为去掉了B中有而A中没有出现的，所以B'中的代号全部对应A中的数 ##

## 设B'的一个子集p，那么将p由代号翻译成原来数字后一定是A的一个子集（不过在A中顺序不确定） ##

## B'的LIS时B‘中一个上升的子集即顺序号上升的子集 即 该子集在A中是按从左到右的顺序的 ##

## 所以它是A与B的公共子序列 ##

## 又因为LIS最长，所以公共子序列最长即最长公共子序列 ##

## 参考：[https://www.cnblogs.com/FuTaimeng/p/5410465.html。][https_www.cnblogs.com_FuTaimeng_p_5410465.html] ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 250 * 250;
    const int INF = 1000000000;
    int S[maxn], g[maxn], d[maxn]; // LIS所需
    int num[maxn]; // num[x]为整数x的新编号,num[x]=0表示x没有在A中出现过
    
    int main() {
      int T;
      scanf("%d", &T);
      for(int kase = 1; kase <= T; kase++) {
        int N, p, q, x;
        scanf("%d%d%d", &N, &p, &q);
        memset(num, 0, sizeof(num));
        for(int i = 1; i <= p+1; i++) { scanf("%d", &x); num[x] = i; }
        int n = 0;
        for(int i = 0; i < q+1; i++) { scanf("%d", &x); if(num[x]) S[n++] = num[x]; }
    
        // 求解S[0]...S[n-1]的LIS
        for(int i = 1; i <= n; i++) g[i] = INF;
        int ans = 0;
        for(int i = 0; i < n; i++) {
          int k = lower_bound(g+1, g+n+1, S[i]) - g; // 在g[1]~g[n]中查找
          d[i] = k;
          g[k] = S[i];
          ans = max(ans, d[i]);
        }
        printf("Case %d: %d\n", kase, ans);
      }
      return 0;
    }

[https_www.cnblogs.com_FuTaimeng_p_5410465.html]: https://www.cnblogs.com/FuTaimeng/p/5410465.html