UVA 10635 Prince and Princess (LCS优化转LIS)

待我称王封你为后i 2023-08-17 15:20 79阅读 0赞

题意：求两个串的最长公共子序列 LCS。

思路：数据量比较大，O(n^2)的dp不够快。但每组数据中的数各不相同，可以利用这一点转化成求最大上升子序列 LIS

就样例来说 A\{1 7 5 4 8 3 9\}， B\{1 4 3 5 6 2 8 9\}，按照A的顺序进行映射：A\{1,2,3,4,5,6,7\} B\{1,4,6,3,0,0,5,7\}

于是问题转化为求B的LIS，可以在O(nlogn)求出。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N=255*255;
    int data[N],stack[N],hash[N];
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		memset(hash,0,sizeof(hash));
    		int n,p,q;
    		scanf("%d%d%d",&n,&p,&q);
    		int i,id=0,x,len=0;
    		for (i=1;i<=p+1;i++)
    		{
    			scanf("%d",&x);
    			hash[x]=i;
    		}
    		for (i=0;i<=q;i++)
            {
    			scanf("%d",&x);
    			if (hash[x])
    				data[id++]=hash[x];
    		}
    		stack[0]=data[0];
    		for (i=1;i<id;i++)
    			if (data[i]>stack[len])
    				stack[++len]=data[i];
    			else
    			{
    				int pos=lower_bound(stack,stack+len,data[i])-stack;
    				stack[pos]=data[i];
    			}
    		printf("Case %d: %d\n",Cas,len+1);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，79人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVa 10635（lcs转lis优化模板）王子和公主

例题27 王子和公主（Prince and Princess, UVa 10635）有两个长度分别为p＋1和q＋1的序列，每个序列中的各个元素互不相同，且都是1

矫情吗；*/ 2024年02月17日 23:20/ 0 赞/ 32 阅读

相关 UVA 10635 Prince and Princess (LCS优化转LIS)

题意：求两个串的最长公共子序列 LCS。思路：数据量比较大，O(n^2)的dp不够快。但每组数据中的数各不相同，可以利用这一点转化成求最大上升子序列 LIS 就样例来说

待我称王封你为后i/ 2023年08月17日 15:20/ 0 赞/ 80 阅读

相关【LeetCode】动态规划问题：LCS 与 LIS 问题

LIS 问题 [300. 最长递增子序列][300.] 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不

Myth丶恋晨/ 2022年10月29日 09:13/ 0 赞/ 118 阅读

相关 HDU Ignatius and the Princess III

include <stdio.h> include <string.h> int main(int argc, char argv[]) {

r囧r小猫/ 2022年05月30日 12:38/ 0 赞/ 157 阅读

相关 HDU-Ignatius and the Princess IV

Ignatius and the Princess IV Problem Description "OK, you are not too bad,

太过爱你忘了你带给我的痛/ 2022年05月28日 01:09/ 0 赞/ 123 阅读

相关 Ignatius and the Princess II

给你N个整数，分别是1，2，3，。。。N。问你全排列的第M个排列为多少？ Input The input contains several test cases. Ea

「爱情、让人受尽委屈。」/ 2022年05月15日 05:20/ 0 赞/ 124 阅读

相关 Ignatius and the Princess IV（map）

Problem Description “OK, you are not too bad, em… But you can never pass the next test

待我称王封你为后i/ 2022年03月02日 04:06/ 0 赞/ 129 阅读

相关 uva10635(最长上升子列)

题意：给出两个数列，每个数列的数都不同，求两个数列的最长公共子列(LCS)，输出长度。分析：LCS转化为LIS。因为两个数组中每个数都不同，所以先将A数组按顺序对应1,2,

青旅半醒/ 2021年12月22日 06:39/ 0 赞/ 122 阅读

相关 uva10635Prince and Princess(LIS)

题意：求最长相同公共子序列。分析：《训练指南》P66，本题是一道经典的题目，巧妙的将LCS问题转化为LIS问题。这种题目的一个特定就是其中一个序列的所有元素均不相同。

Dear 丶/ 2021年12月17日 03:17/ 0 赞/ 201 阅读

相关 bzoj1264 基因匹配Match （lcs转lis lcs（nlogn））

基因匹配Match 内存限制：256 MiB 时间限制：1000 ms 标准输入输出题目描述基因匹配（match）卡卡昨天晚上做梦梦见他和可可

偏执的太偏执、/ 2021年12月12日 02:39/ 0 赞/ 175 阅读