首页 > 代码库 > BestCoder Round #87 1003 LCIS[序列DP]

BestCoder Round #87 1003 LCIS[序列DP]

2024-08-15 10:06:45   212人阅读

LCIS

 
 Accepts: 109
 
 Submissions: 775
 Time Limit: 4000/2000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
问题描述
Alex有两个序列a1a2...ana?1??,a?2??,...,a?n??和b1b2...bmb?1??,b?2??,...,b?m??. 他想找到它们的最长公共递增子序列, 并且这个子序列的值是连续的(xx1...y1yx,x+1,...,y−1,y).
输入描述
输入包含多组数据, 第一行包含一个整数TT表示测试数据组数. 对于每组数据:第一行包含两个整数nn和mm 1nm100000(1≤n,m≤100000)表示两个序列的长度. 第二行包含nn个整数: a1a2...ana?1??,a?2??,...,a?n?? 1ai106(1≤a?i??≤10?6??). 第三行包含mm个整数: b1b2...bmb?1??,b?2??,...,b?m?? 1bi106(1≤b?i??≤10?6??).输入最多有10001000组数据, 并且所有数据中nn与mm的和不超过21062×10?6??.
输出描述
对于每组数据, 输出一个整数表示长度.
输入样例
33 31 2 33 2 110 51 23 2 32 4 3 4 5 6 11 2 3 4 51 121
输出样例
150
本题多了一个要求，上升必须是依次递增
一开始还想用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+5,V=1e6+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;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=0,la=0,lb=0;        for(int i=1;i<=n;i++) a[i]=read();//la=max(la,a[i]=read());        for(int i=1;i<=m;i++) b[i]=read();//lb=max(lb,b[i]=read());        for(int i=1;i<=n;i++)            f[a[i]]=max(f[a[i]],f[a[i]-1]+1);        for(int i=1;i<=m;i++){            g[b[i]]=max(g[b[i]],g[b[i]-1]+1);            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=1;i<=n;i++) f[a[i]]=0;        for(int i=1;i<=m;i++) g[b[i]]=0;    }    return 0;}
 
 
BestCoder Round #87 1003 LCIS[序列DP]






























        

            
                
                  
                
                

                    联系

                    我们