LCIS
Accepts: 109
Submissions: 775
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
Alex有两个序列a1a2...ana1,a2,...,an和b1b2...bmb1,b2,...,bm. 他想找到它们的最长公共递增子序列, 并且这个子序列的值是连续的(xx1...y1yx,x+1,...,y−1,y).
输入描述
输入包含多组数据, 第一行包含一个整数TT表示测试数据组数. 对于每组数据: 第一行包含两个整数nn和mm 1nm100000(1≤n,m≤100000)表示两个序列的长度. 第二行包含nn个整数: a1a2...ana1,a2,...,an 1ai106(1≤ai≤106). 第三行包含mm个整数: b1b2...bmb1,b2,...,bm 1bi106(1≤bi≤106). 输入最多有10001000组数据, 并且所有数据中nn与mm的和不超过21062×106.
输出描述
对于每组数据, 输出一个整数表示长度.
输入样例
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
输出样例
1
5
0
本题多了一个要求，上升必须是依次递增
一开始还想用f[i]表示以a[i]结尾，然而并不方便(应该能做，开一个mx[i]表示值大小为i的f值最大的编号)
直接f[i]表示a以i结尾的"LIS",g[i]表示b的
处理g时顺便更新答案行了 ps：代码里有一些奇怪的卡常请无视
//
// main.cpp
// bc87-1003
//
// Created by Candy on 10/1/16.
// Copyright © 2016 Candy. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
const int N=1e5+,V=1e6+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x;
}
int T,n,m,a[N],b[N],f[V],g[V];
int main(int argc, const char * argv[]){
T=read();
while(T--){
n=read();m=read();
int ans=,la=,lb=;
for(int i=;i<=n;i++) a[i]=read();//la=max(la,a[i]=read());
for(int i=;i<=m;i++) b[i]=read();//lb=max(lb,b[i]=read());
for(int i=;i<=n;i++)
f[a[i]]=max(f[a[i]],f[a[i]-]+);
for(int i=;i<=m;i++){
g[b[i]]=max(g[b[i]],g[b[i]-]+);
ans=max(ans,min(f[b[i]],g[b[i]]));
}
printf("%d\n",ans);//la++;lb++;
//memset(f,0,la*sizeof(int));
//memset(g,0,lb*sizeof(int));
for(int i=;i<=n;i++) f[a[i]]=;
for(int i=;i<=m;i++) g[b[i]]=;
}
return ;
}