LCIS
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 710 Accepted Submission(s): 323
Problem Description
Alex has two sequences
a1,a2,...,an
and
b1,b2,...,bm
. He wants find a longest common subsequence that consists of consecutive values in increasing order.
Input
There are multiple test cases. The first line of input contains an integer
T
, indicating the number of test cases. For each test case:
The first line contains two integers
n
and
m
(1≤n,m≤100000)
-- the length of two sequences. The second line contains
n
integers:
a1,a2,...,an
(1≤ai≤106)
. The third line contains
n
integers:
b1,b2,...,bm
(1≤bi≤106)
.
There are at most
1000
test cases and the sum of
n
and
m
does not exceed
2×106
.
Output
For each test case, output the length of longest common subsequence that consists of consecutive values in increasing order.
Sample Input
3
3 3
1 2 3
3 2 1
10 5
1 23 2 32 4 3 4 5 6 1
1 2 3 4 5
1 1
2
1
Sample Output
1
5
0
Source
BestCoder Round #87
My Solution
dp、LCIS、 最长公共上升子序列且每次递增 1
状态定义：dpa[i] 表示以ai结尾的每次递增 1 的 LIS 的
最大长度
，
dpb[j] 表示以bi结尾的的每次递增 1 的 LIS 的
最大长度
，
边界：当 i == 1时， dpa[i] = 1, dpb[i] = 1;
状态转移方程： dpa[i] = dpa[Inda[a[i] - 1]] + 1; dpa[i] = max(dpa[i], dpa[Inda[a[i]]]);
Inda[a[i]] = i;
dpb[i] = dpb[Indb[b[i] - 1]] + 1; dpb[i] = max(dpb[i], dpb[Indb[b[i]]]);
Indb[b[i]] = i;
求ans：ans = max(ans, min(dpa[i], dpb[Indb[a[i]]])); // 1 <= i <= n
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;
int dpa[maxn], dpb[maxn], a[maxn], b[maxn];
//map<int, vector<int> > Inda, Indb;
map<int, int> Inda, Indb; //维护最后一个ai的下标
int main()
{
#ifdef LOCAL
freopen("c.txt", "r", stdin);
//freopen("c.out", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false); cin.tie(0);
int T, n, m, ans;
cin >> T;
while(T--){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
//Inda[a[i]].push_back(i);
}
for(int i = 1; i <= m; i++){
cin >> b[i];
//Indb[b[i]].push_back(i);
}
int sz;
for(int i = 1; i <= n; i++){
if(i != 1){
dpa[i] = dpa[Inda[a[i] - 1]] + 1;
dpa[i] = max(dpa[i], dpa[Inda[a[i]]]);
}
else dpa[i] = 1;
Inda[a[i]] = i;
}
for(int i = 1; i <= m; i++){
if(i != 1){
dpb[i] = dpb[Indb[b[i] - 1]] + 1;
dpb[i] = max(dpb[i], dpb[Indb[b[i]]]);
}
else dpb[i] = 1;
Indb[b[i]] = i;
}
ans = 0;
for(int i = n; i > 0; i--){
if(Indb[a[i]] != 0){
ans = max(ans, min(dpa[i], dpb[Indb[a[i]]]));
}
}
cout << ans << endl;
Inda.clear(); Indb.clear();
}
return 0;
}
Thank you!
------from
ProLights
转载请注明原文地址: https://ju.6miu.com/read-1201422.html
