UVa 10635(lcs转lis优化模板)王子和公主

2017年07月15日 11点热度 0人点赞 0条评论

例题27 王子和公主(Prince and Princess, UVa 10635)
有两个长度分别为p+1和q+1的序列, 每个序列中的各个元素互不
相同, 且都是1~n2之间的整数。 两个序列的第一个元素均为1。 求出A和
B的最长公共子序列长度。
【输入格式】
输入的第一行为数据组数T(T≤10) 。 每组数据包含3行, 第一行为3
116个整数n, p, q(2≤n≤250, 1≤p, q≤n2) ; 第二行包含序列A, 其中第一
个数为1, 其元素两两不同, 且都是1~n2之间的整数; 第三行包含序列
B, 格式同序列A。
【输出格式】
对于每组数据, 输出A和B的最长公共子序列的长度。
【分析】
本题是LCS问题, 但因为p和q可以高达2502=62500, O(pq) 的算法
显然太慢。 注意到A序列中所有元素均不相同, 因此可以把A中元素重新
编号为1~p+1。 例如, 样例中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} , 其中0表示A中没有出现过
(事实上, 可以直接删除这些元素, 因为它们肯定不在LCS中) 。 这样,
新的A和B的LCS实际上就是新的B的LIS。 由于LIS可在O(nlogn) 时间内

解决, 因此本题也可在O(nlogn) 时间内得到解决。 代码如下。

/*优化lcs的时间复杂度,把LCS(最长公共子序列)变成LIS(最长上升子序列)
时间复杂度由log(n*n) 变为log(n*log n)
*/
#include
#include
#include
#include
using namespace std;
const int mn=250*250+5;
int s[mn],d[mn],num[mn],g[mn];
int N,p,q;
int main()
{
    int T,x;
    scanf("%d",&T);
    for(int e=1;e<=T;e++)
    {
        scanf("%d%d%d",&N,&p,&q);
        int n=0;
        memset(num,0,sizeof(num));
        for(int i=1;i<=p+1;i++)
        {
            scanf("%d",d+i);
            num[d[i]]=i;
        }
        for(int i=0;i

未经允许不得转载!UVa 10635(lcs转lis优化模板)王子和公主

update

纸上得来终觉浅, 绝知此事须躬行。