UVa 10635 - Prince and Princess

题目地址

描述

两个长度为$p + 1$的序列$\text{A}$和$q + 1$的序列$\text{B}$,每个序列中的元素各不相同,且都是$1 \sim n^{2}$之间的整数 $(2 \leq n \leq 250)$。两个序列开始的第一个元素都是$1$,求$A$和$B$的最长公共子序列。

分析

这道题的思想很棒棒呀QAQ

就是LCS问题,但是$\Theta(pq)$的时间复杂度承受不了,要考虑如何来优化。

仔细看一遍体面我们发现有描述 :” 每个序列中的元素各不相同 “ 。

我们考虑用$1 \sim p + 1$的数字来对$\text{A}$重新标号,举一个例子:

- 1 2 3 4 5 6 7
A 1 7 5 4 8 3 9
A’ 1 2 3 4 5 6 7

那么原来的序列$\text{A}$相当于映射到序列$\text{A’}$,然后我们用序列$\text{B’}$表示原序列$\text{B}$通过已知的映射关系解出的新序列,如下:

- 1 2 3 4 5 6 7 8
B 1 4 3 5 6 2 8 9
B’ 1 4 6 3 0 0 5 7

那么我们相当于将原来的求最长公共子序列的问题转化成为了求序列$\text{B’}$的最长上升子序列的长度,而最长上升子

序列问题是可以在$\Theta(nlogn)$的时间复杂度求出来的。

令$dp[i]$为前$i$个数中最大的数的位置,那么把$dp$数组先初始化为$\infty$。每次在$dp$数组中查询第一个大于等于$a[i]$的位

置$(pos)$,然后令$dp[pos] = a[i]$,并更新答案$ans = max(ans, pos)$。

因为这里的$dp$数组保证递增,那么我们可以用二分查找来找位置,复杂度为$\Theta(logn)$,扫一遍数组$a$的时间复杂度

为$\Theta(n)$,所以时间复杂度为$\Theta(nlogn)$。

注意: 子序列与子串的区别在于子序列不要求在原字符串中是连续的,而子串要求在原字符串中的连续的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//  Created by ZJYelizaveta on 2017年08月26日 星期六 10时47分50秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 250 + 3;
const int MAXNODE = MAX_N * MAX_N;
const int INF = 0x3f3f3f3f;
int testCase;
int n, p, q;
int a[MAXNODE];
map<int, int> M;
int dp[MAXNODE];

int main()
{
testCase = readIn();
for (int num = 1; num <= testCase; ++num) {
M.clear();
n = readIn(), p = readIn(), q = readIn();
for (int i = 1; i <= p + 1; ++i) {
M[readIn()] = i;
}
memset(a, 0, sizeof a);
for (int i = 1; i <= q + 1; ++i) {
int num = readIn();
a[i] = M[num];
}
// for (int i = 1; i <= q + 1; ++i) printf("%d ", a[i]); printf("\n");
int cnt = q + 1, ans = 0;
memset(dp, INF, sizeof dp);
for (int i = 1; i <= cnt; ++i) {
int pos = lower_bound(dp + 1, dp + cnt + 1, a[i]) - dp;
dp[pos] = a[i];
ans = max(ans, pos);
}
printf("Case %d: %d\n", num, ans);
}
return 0;
}
Partager