LCS转LIS
题意 -> 即题目
5
3 2 1 4 5
1 2 3 4 5
-----> 3 <----- (145,245,345…)
思路
用一个map将其中一个序列自定义大小:
map<int,int> mp;
for(int i = 1; i <= n; i ++) mp[b[i]] = i;
再把另一个序列按照新的大小规则更新一遍
for(int i = 1; i <= n; i ++) a[i] = mp[a[i]];
接下来就是简单二分LIS问题
贴上完整代码:
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector")
#define endl '\n'
#define int long long
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define Yes cout << "Yes" << endl
#define PII pair<int,int>
#define x first
#define y second
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define SOLVE int T;cin >> T;while(T--) SV()
using namespace std;
int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);}
int lcm(int a, int b) {return a * b / gcd(a, b);}
int ksm(int a, int b, int p) {int res = 1;while(b){if(b & 1)res = res * a % p;b >>= 1;a = a * a % p;}return res;}
bool is_prime(int x){if(x < 2) return false; if(x == 2)return true;for(int i = 2; i * i <= x; i ++) if(x % i == 0)return false;return true;}
//ksm(a , p - 2, p);!(a % p) -> ok;
const int N = 1e5 + 10;
void SV() {
int n;
cin >> n;
vector<int> a(n + 1) , b(n + 1);
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) cin >> b[i];
map<int,int> mp;
for(int i = 1; i <= n; i ++) mp[b[i]] = i;
for(int i = 1; i <= n; i ++) a[i] = mp[a[i]];
vector<int> f(n + 1) , q(n + 1);
int len = 0;
q[0] = 0;
for(int i = 1; i <= n; i ++) {
int l = 0 , r = len + 1;
while(l + 1 < r) {
int mid = l + r >> 1;
if(q[mid] < a[i]) l = mid;
else r = mid;
}
len = max(r , len);
q[r] = a[i];
}
cout << len << endl;
}
signed main(){IOS;SV();}
牛逼
牛逼
牛逼