UVA 10635 - Prince and Princess （ LCS 转换为LIS ）

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1576

题        意：给你两个数组，找出最长公共子序列。

思        路：由于数组太大，所以不可以用常规方法。因此有个巧妙的转换，把A中的元素重新按1~p+1编号，

                   同时B也相同的映射编号，由于A为递增序列，所以LCS就是B中最长递增子序列，即LIS.这样就

                   转换成求B的LIS问题，可以在O(nlogn)的时间内解决。

代码如下：

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define maxn 62505
int s[maxn], g[maxn], d[maxn], vis[maxn];
int main()
{int T;scanf ( "%d", &T );int cas=1;while( T-- ){int p, q, n, x;memset( vis, 0, sizeof(vis) );scanf ( "%d %d %d", &n, &p, &q );for( int i = 1; i <= p&#

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！