C++

C++ – LCS 最长公共子序列 洛谷 P1439

_Redstone_c_

基本解法

\Omicron(N^2)

譬如给定 2 个序列：

1 2 3 4 5
3 2 1 4 5

试求出最长的公共子序列。

显然长度是 3 ，包含 3 4 5 三个元素（不唯一）

我们可以用 dp[i][j] 来表示第一个串的前 i 位，第二个串的前 j 位的 LCS 的长度，

那么很容易想到状态转移方程：

如果当前的 A1[i]A1[i]A1[i] 和 A2[j]A2[j]A2[j] 相同（即是有新的公共元素）,那么

dp[i][j] = \max(dp[i][j], dp[i − 1][j − 1] + 1)

如果不相同，即无法更新公共元素，考虑继承：

dp[i][j] = \max(dp[i − 1][j], dp[i][j − 1])

那么代码:

#include<iostream>
using namespace std;
int dp[1001][1001], a1[2001], a2[2001], n, m;
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) scanf("%d", &a1[i]);
    for(int i = 1; i <= m; i++) scanf("%d", &a2[i]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(a1[i] == a2[j])
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
        }
    cout << dp[n][m];
}

AC解法 (非上面优化)

\Omicron(N \log N)

这题有一个神奇的限定： 给出 1-n 的两个排列。

可以看出数列A和B中的数值不会重复。

所以可以这样想，用A中数值所在位次替换B中相应数字的值，然后求最长上升子序列就可以了。

例如 A = [3, 2, 1, 4, 5] B = [1, 2, 3, 4, 5] 可得 B = [3, 2, 1, 4, 5]

最长上升子序列为 3 ，答案正是 3

#include <cstdio>
using namespace std;
const int MAXN = 100000 + 100;
int n, back;
int A[MAXN], B[MAXN], T[MAXN];
int queue[MAXN];
int bs(int start, int end, int x) {
    if(start >= end) return start;
    int mid = (end - start) / 2 + start;
    if(queue[mid] >= x) return bs(start, mid, x);
    return bs(mid + 1, end, x);
}
void add(int x) {
    int temp = bs(0, back, x);
    queue[temp] = x;
    if(temp == back) back++;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &B[i]);
    for(int i = 1; i <= n; i++) T[A[i]] = i;
    for(int i = 1; i <= n; i++) add(T[B[i]]);
    printf("%d", back);
    return 0;
}

发表回复