【PAT 1045】 Favorite Color Stripe 最长公共子序列LCS

2024-04-05 06:18

本文主要是介绍【PAT 1045】 Favorite Color Stripe 最长公共子序列LCS,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1045. Favorite Color Stripe (30)

时间限制
200 ms
内存限制
32000 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

Eva is trying to make her own color stripe out of a given one. She would like to keep only her favorite colors in her favorite order by cutting off those unwanted pieces and sewing the remaining parts together to form her favorite color stripe.

It is said that a normal human eye can distinguish about less than 200 different colors, so Eva's favorite colors are limited. However the original stripe could be very long, and Eva would like to have the remaining favorite stripe with the maximum length. So she needs your help to find her the best result.

Note that the solution might not be unique, but you only have to tell her the maximum length. For example, given a stripe of colors {2 2 4 1 5 5 6 3 1 1 5 6}. If Eva's favorite colors are given in her favorite order as {2 3 1 5 6}, then she has 4 possible best solutions {2 2 1 1 1 5 6}, {2 2 1 5 5 5 6}, {2 2 1 5 5 6 6}, and {2 2 3 1 1 5 6}.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=200) which is the total number of colors involved (and hence the colors are numbered from 1 to N). Then the next line starts with a positive integer M (<=200) followed by M Eva's favorite color numbers given in her favorite order. Finally the third line starts with a positive integer L (<=10000) which is the length of the given stripe, followed by L colors on the stripe. All the numbers in a line a separated by a space.

Output Specification:

For each test case, simply print in a line the maximum length of Eva's favorite stripe.

Sample Input:
6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6
Sample Output:
7
题意:

题目抽象出来就是寻找两个序列的最长公共子序列, 但是公共部分允许元素重复出。

分析:

最长公共子序列(LCS,Longest Common Subsequence的变种-公共部分可以元素重复。



代码:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>using namespace std;//此代码使用前,需删除下面两行+后面的system("PAUSE")
ifstream fin("in.txt");
#define cin finint like[201]={0};
int given[10001]={0};
int len[201][10001]={0};int LCS(int row,int col)
{int i,j;int max;for(i=1;i<=row;i++){for(j=1;j<=col;j++){max = len[i-1][j-1];if(max < len[i][j-1])max = len[i][j-1];if(max < len[i-1][j])max = len[i-1][j];		//先求出左边、上边、左上边 三个值中的最大值if(like[i]==given[j]){				//如果相等,则将最大值+1len[i][j] = max+1;}else{len[i][j] = max;}			}}return len[row][col];
}int main()
{int n,m,l;cin>>n>>m;int i;for(i=0;i<m;i++)cin>>like[i+1];cin>>l;for(i=0;i<l;i++)cin>>given[i+1];cout<<LCS(m,l)<<endl;system( "PAUSE");return 0;
}

这篇关于【PAT 1045】 Favorite Color Stripe 最长公共子序列LCS的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/877831

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

uva 10066 LCS

题意: 最长公共子序列。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr