最长公共子序列问题
查看原帖
最长公共子序列问题
597063
xiaoxiao030522楼主2022/10/20 22:48

P1439最长公共子序列的问题,按照dalao说的那样先把最长公共子序列问题转化为最长上升子序列问题,但是提交上去所有测试点都RE了,下载了测试数据在本地运行也没有任何问题,不太明白是为什么,求解答orz

#include <stdio.h>

#define MAX 10100

int p1[MAX];
int p2[MAX];

int q1[MAX];
int q2[MAX];

int ans[MAX];
int top = 0;

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &p1[i]);
        q1[p1[i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &p2[i]);
        q2[i] = q1[p2[i]];
    }
    for (int i = 1; i <= n; ++i) {
        if (q2[i] > q2[top]) {
            top++;
            ans[top] = q2[i];
        } else {
            int l = 1, r = top, tmp = q2[i], mid;
            while (l < r) {
                mid = (l + r) / 2;
                if (ans[mid] > tmp)
                    r = mid;
                else
                    l = mid + 1;
            }
            ans[mid] = tmp;
        }
    }
    printf("%d", top);
    return 0;
}
2022/10/20 22:48
加载中...