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 ;
}