网站修改联系方式,成都专业网站建设机构,郑州网站设计汉狮,wordpress new图标题意#xff1a;给定两个长度为p1和q1的序列#xff0c;求两个序列的LCS。 思路#xff1a;如果直接使用朴素的LCS算法则O#xff08;pq#xff09;会超时#xff0c;可以把A中出现的元素编码#xff0c;然后映射到B#xff08;只保留AB都存在的元素#xff09;…题意给定两个长度为p1和q1的序列求两个序列的LCS。 思路如果直接使用朴素的LCS算法则Opq会超时可以把A中出现的元素编码然后映射到B只保留AB都存在的元素这样就转化为求B的LIS问题了Onlogn。 code #include bits/stdc.h
using namespace std;const int N250*250;
const int INF0x3f3f3f3f;int s[N],f[N],d[N],id[N];int main()
{int T;scanf(%d,T);for (int ca1;caT;ca){int N,p,q,x;scanf(%d%d%d,N,p,q);memset(id,0,sizeof(id));for (int i1;ip1;i) {scanf(%d,x);id[x]i;}int n0;for (int i0;iq1;i){scanf(%d,x);if (id[x]) s[n]id[x];}for (int i1;in;i) f[i]INF;int ans0;for (int i0;in;i){int plower_bound(f1,fn1,s[i])-f;d[i]p;f[p]s[i];ansmax(ans,d[i]);}printf(Case %d: %d\n,ca,ans);}}
