14027: 【原4027】贝学长摆贝壳

题目

题目描述

author: 李江贝 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4027 

Description

国庆节到了，贝学长决定来一场面向大海，春暖花开的旅行。在海边，贝学长童话般地遇到了一条小人鱼。小人鱼给了贝学长两堆完全一样的贝壳，每份贝壳里的贝壳图案各不相同。小人鱼告诉贝学长，如果把这两份贝壳摆成两串，会有幸运发生。然而，等贝学长摆好之后，小人鱼才告诉他，这两串贝壳必须图案顺序完全相同，魔力才有效；并且，她要求贝学长只能往下取，不能往上放。由于贝壳越多幸运值就越大，贝学长想知道，在他取下不符合要求的贝壳之后，要想幸运值最大，最多还剩多少贝壳。（即这两串贝壳的公共序列最长是多长，剩下的贝壳不需要连续。其中不同图案由不同数字代替。）

Input Format

第一行是一个数n，代表每堆贝壳的数量， 接下来两行，每行为n个数，为自然数1-n的一个排列，代表贝壳的图案。

• 100%的数据 0<n<100000
• 50%的数据 0<n<1000

Output Format

一个数，即每串贝壳的数量。

Sample Input

5
2 3 5 1 4 
1 5 2 3 4

Sample Output

3

FineArtz's solution

/* 贝学长摆贝壳 */
#include <iostream>
using namespace std;

int reflection[100005] = {0}, a[100005] = {0}, ans[100005] = {0};

int bisearch(int low, int high, int sought){
    if (low >= high) return low;
    int m = (low + high) / 2;
    if (ans[m] < sought) return bisearch(m + 1, high, sought);
    else return bisearch(low, m, sought);
}

int main(){
    int n, len = 0, j = 0, t = 0;;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> t;
        reflection[t] = i;
    }
    for (int i = 1; i <= n; ++i){
        cin >> t;
        a[i] = reflection[t];
        if (a[i] > ans[len]) j = ++len;
        else j = bisearch(1, len, a[i]);
        ans[j] = a[i];
    }
   // for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
    //cout << endl;
    cout << len << endl;
    return 0;
}

ligongzzz's solution

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

int n;
int a1[100009] = { 0 }, a2[100009] = { 0 };
int belong[100009] = { 0 };
int f[100009], b[100009], len;

int mid_find(int left, int right, int val) {
    int right_ans = right;
    --right;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (val > b[mid]) {
            left = mid + 1;
        }
        else if (val <= b[mid]) {
            right_ans = mid;
            right = mid - 1;
        }
    }
    return right_ans;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a1[i]);
        belong[a1[i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a2[i]);
    }

    for (int i = 1; i <= n; ++i)
    {
        if (belong[a2[i]] > b[len])
        {
            b[++len] = belong[a2[i]];
            f[i] = len;
            continue;
        }
        int k = mid_find(1, len + 1, belong[a2[i]]);
        b[k] = belong[a2[i]];
        f[i] = k;
    }
    printf("%d\n", len);
    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e5 + 100;

int a[maxN] = {0}, b[maxN] = {0}, c[maxN] = {0};

int LIS(int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, temp, ans;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        c[temp] = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        a[i] = c[temp];
    }

    ans = LIS(n);

    cout << ans;

    return 0;
}

int LIS(int n) {
    int ans = 1;
    b[0] = a[1];

    for (int i = 1; i < n; i++) {
        int left = 0, right = ans - 1, mid = (left + right) / 2;

        while (left < right) {
            if (a[i + 1] == b[mid]) {
                break;
            } else if (a[i + 1] < b[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
            mid = (left + right) / 2;
        }

        if (a[i + 1] > b[mid]) {
            mid++;
        }

        if (mid == ans) {
            b[ans++] = a[i + 1];
        } else {
            b[mid] = a[i + 1];
        }
    }

    return ans;
}

q4x3's solution

/**
 * lcs->lis
 * nlogn
 * lis[i]表示长度为i的上升子序列最后一位最小是多少
 **/
#include <iostream>
#include <stdio.h>

using namespace std;

int inv[100233], lis[100233], seq[100233], n, len, tmp;

int lower_bound(int lo, int hi, int a) {
    if(lo >= hi) return lo;
    int mi = (lo + hi) >> 1;
    if(lis[mi] < a) return lower_bound(mi + 1, hi, a);
    else return lower_bound(lo, mi, a);
}

int main() {
    scanf("%d", &n);
    for(int i = 1;i <= n;++ i) {
        scanf("%d", &tmp);
        inv[tmp] = i;
    }
    for(int i = 1;i <= n;++ i) {
        scanf("%d", &tmp);
        seq[i] = inv[tmp];
    }
    for(int i = 1;i <= n;++ i) {
        if(seq[i] > lis[len]) {
            lis[++ len] = seq[i];
        } else {
            int tmp1 = lower_bound(1, len, seq[i]);
            lis[tmp1] = seq[i];
        }
    }
    printf("%d\n", len);
}

victrid's solution

#include <cstdio>
#include <iostream>
using namespace std;

int dseq[100010];
int qseq[100010];
int dp[100010] = {0};

int bifind(int left, int right, int val) {
    int ans = right;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (val > dp[mid]) {
            left = mid + 1;
        } else if (val <= dp[mid]) {
            ans   = mid;
            right = mid - 1;
        }
    }
    return ans;
}

int main() {
    int n, pc;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &pc);
        dseq[pc] = i;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &pc);
        qseq[dseq[pc]] = i;
    }
    //now find the longest increase sequence
    int len = 1, lhs, rhs, pos;
    dp[1]   = qseq[1];
    for (int i = 2; i <= n; i++) {
        if (qseq[i] > dp[len]) {
            dp[++len] = qseq[i];
            continue;
        }
        dp[bifind(1, len, qseq[i])] = qseq[i];
    }
    printf("%d", len);
    return 0;
}