Uva 10635 - Prince and Princess 问题转化，元素互不相同（在自身序列中独特）的两个数列的LCS，LIS 难度: 2

时间：2024-10-26 23:03:20

题目

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

题意

两个元素互不相同（在自身数列中互不相同）的数列，求二者的LCS。

思路

如刘书，

非常棒的思路：

1. 明显LCS问题只要关注两个数列的交集，利用第一个数列a的元素，对第二个数列b中的元素重编号（b元素中没有出现在a数列中的可以忽略）问题就转化为最长上升子序列问题。

2. 使用lower_bound不断维护数组leftNum，其中leftNum[i]是上升子序列延伸到i+1长度时最后一个元素（也是最大的那个元素，比如2,3,5中的5)的最小值

感想

1. 反射性地想用树状数组维护leftNum

代码

#include <algorithm>

#include <cassert>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <string>

#include <tuple>

#define LOCAL_DEBUG

using namespace std;

typedef pair<int, int> MyPair;

const int MAXN =  *  + ;

int b[MAXN];

int leftNum[MAXN];

int main() {

#ifdef LOCAL_DEBUG

    freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);

    //freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);

#endif // LOCAL_DEBUG

    int T;

    scanf("%d", &T);

    for (int ti = ; ti <= T; ti++) {

        int n, p, q;

        scanf("%d%d%d", &n, &p, &q);

        map<int, int> a2ind;

        for (int i = ; i <= p; i++) {

            int tmp;

            scanf("%d", &tmp);

            a2ind[tmp] = i;

        }

        int blen = ;

        for (int i = ; i <= q; i++) {

            int tmp;

            scanf("%d", &tmp);

            if (a2ind.count(tmp) != ) {

                b[blen++] = a2ind[tmp];

            }

        }

        int leftlen = ;

        for (int i = ; i < blen; i++) {

            int ind = lower_bound(leftNum, leftNum + leftlen, b[i]) - leftNum;

            leftNum[ind] = b[i];

            if (ind == leftlen)leftlen++;

        }

        printf("Case %d: %d\n", ti, leftlen);

    }

    return ;

}

相关文章