广告行业包括网站建设吗,那个网站百度收录快,贵州建设厅网站建筑企业公示栏,苏州招聘网站开发标题效果#xff1a;有两个长度p1和q1该序列。的各种元素的每个序列不是相互同。并1~n^2之间的整数。个序列的第一个元素均为1。求出A和B的最长公共子序列长度。 分析#xff1a;本题是LCS问题#xff0c;可是p*q62500,O(pq)的算法显然会LE。在这里有一个条件#xff0… 标题效果有两个长度p1和q1该序列。的各种元素的每个序列不是相互同。并1~n^2之间的整数。个序列的第一个元素均为1。求出A和B的最长公共子序列长度。 分析本题是LCS问题可是p*q62500,O(pq)的算法显然会LE。在这里有一个条件每一个序列中的各个元素互不同样所以能够把A中元素又一次编号为1~p1。比如例子中A{1,7,5,4,8,3,9}B{1,4,3,5,6,2,8,9}。因此把A又一次编号为{1,2,3,4,5,6,7}。则B就是{1,4,6,3,0,0,5,7}在A中没有出现过的元素一定不会是公共子序列中的元素当中0表示A中没有出现过能够直接删去。这时B{1,4,6,3,5,7}元素的值代表着B中和原A中元素值同样的。在A中的位置。子序列的位置一定要是单调递增的,这样求得的最长子序列才相当于原和的最长公共子序列。由此。成功转化成LIS问题(*∩_∩*)′。求出B的LIS就可以。时间复杂度就能够优化到O(nlogn)了。 以下贴上代码(借鉴lrj巨犇的-) #includeiostream
#includecstring
#includealgorithm
using namespace std;const int maxn 250*250;
const int INF 1e9;
int s[maxn],g[maxn],d[maxn];
int num[maxn]; //num[x]为整数x的新编号。num[x]0表示x没有在A中出现过int main()
{int T;cinT;for(int kase1;kaseT;kase){int N,p,q,x;cinNpq;memset(num,0,sizeof(num));for(int i1;ip1;i){cinx;num[x]i;}int n0;for(int i0;iq1;i){cinx;if(num[x]) s[n]num[x];}//求解s[0]...s[n-1]的LISfor(int i1;in;i) g[i]INF;int ans0;for(int i0;in;i){int klower_bound(g1,gn1,s[i])-g;d[i]k;g[k]s[i];ansmax(ans,d[i]);}coutCase kase: ansendl;}return 0;
}关于lower_bound函数二分查找函数是STL库的。不懂的童鞋请看http://blog.csdn.net/u012198382/article/details/24887181lower_bound说明 版权声明本文博客原创文章。博客未经同意不得转载。 转载于:https://www.cnblogs.com/blfshiye/p/4728927.html
