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

### 题目描述

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

## Input Format

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

## 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;
}
``````