题目大意是求下面两行数组的最长公共子序,但要注意数据范围:250*250,暗示了题目复杂度必须在o(n^2)一下。
一般的dp求LCS复杂度为o(n^2),所以不能用。但很容易想到,两者的LCS包含的元素一定是两者都有的元素,于是可以预处理一下数组,使之不包含两者不公有的元素,而剩下的元素次序不改变。
然后就该着眼于优化。不妨参考一下求加强版最长单调子序列(HOJ 10027 Longest Ordered Subsequence Extention)时,用了一个len数组记录同样长度下处于该位置的最小元素,然后查找时,二分处理,使o(n^2)的复杂度降为了o(nlogn)。
可以这样做,如样例中的第一行数组“1 7 5 4 8 3 9”,经过预处理后变为“1 5 4 8 3 9”,按照里面个元素出现的早晚/位置先后赋权重,使得“1” < “5” < “4” < “8” < “3” < “9”;这样第一列预处理后的数组成了天然的“单增”序列(题目指明不含相同元素)。
根据每个元素的权重,找出第二行数组的最长“单增”子序,即为二者的LCS。
AC代码:
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int T, t, n, p, q;
int i, j, k;
int len;
int ans;
int b[62501], s[62501];
int tb[62501], ts[62501];
int va[62501];
int r[62501];
bool v1[62501], v2[62501];
int b_search(int x, int lt, int rt)
{
while (lt <= rt)
{
int mid = (lt + rt) >> 1;
if (va[r[mid]] < va[x] && va[r[mid+1]] > va[x])
return mid + 1;
else if (va[r[mid]] > va[x])
rt = mid - 1;
else
lt = mid + 1;
}
return 1;
}
void judge(bool *v, int *ta, int length)
{
for (i = 1; i <= length; i++)
{
scanf("%d", &ta[i]);
v[ta[i]] = true;
}
return ;
}
void wrt(int *ta, int *a, int length)
{
for (i = 1, k = 1; i <= length; i++)
{
if (v1[ta[i]] && v2[ta[i]])
{
a[k] = ta[i];
// printf("%d\n", a[k]);
k++;
}
}
// printf("\n");
return ;
}
int main()
{
#ifdef BellWind
freopen("B.in", "r", stdin);
#endif // BellWind
while (~scanf("%d", &T))
{
for (t = 1; t <= T; t++)
{
memset(v1, 0, sizeof(v1));
memset(v2, 0, sizeof(v2));
scanf("%d%d%d", &n, &p, &q);
p++; q++;
judge(v1, tb, p);
judge(v2, ts, q);
wrt(tb, b, p);
wrt(ts, s, q);
len = --k;
// printf("len: %d\n", len);
// for (i = 1; i <= len; i++)
// {
// printf("~%d %d\n", b[i], s[i]);
// }
// printf("\n");
for (i = 1; i <= len; i++) //赋权重
{
va[b[i]] = i;
}
// for (i = 1; i <= len; i++)
// {
// printf("..%d ", va[s[i]]);
// }
// printf("\n\n");
r[1] = s[1];
ans = 1;
for (i = 2; i <= len; i++)
{
if (va[s[i]] > va[r[ans]])
{
ans++;
r[ans] = s[i];
// printf("#%d\n", s[i]);
}
else if (va[s[i]] < va[r[1]])
{
r[1] = s[i];
}
else
{
int j = b_search(s[i], 1, ans);
r[j] = s[i];
}
}
printf("Case %d: %d\n", t, ans);
}
}
return 0;
}