- 浏览: 37769 次
文章分类
- 全部博客 (41)
- 卧鸟个去 (2)
- Transform (2)
- Mathmatic (9)
- Plant-Tree (7)
- Data-Struct (12)
- Red-Black-Tree (1)
- Radix-Tree (1)
- Trie (2)
- String (4)
- BST (2)
- Amazing-Union-Find-Set (1)
- HDU (27)
- OJ (32)
- BFS (3)
- Pretty-Suffix-Array (2)
- POJ (6)
- Graceful-Segment-Tree (2)
- Geometry (6)
- Priority-Queue (2)
- Dynamic-Programing (1)
- DP (3)
- LCS (1)
- Convex-Hull (2)
- Triangulation (1)
- DFS (3)
- Combinatorial-Mathematics (2)
- Big-Number (1)
- Statistic (3)
- STL (1)
- Shortest-Path (3)
- ZOJ (1)
- Leftist-Tree (1)
- Prime (1)
- Binary-Index-Tree (1)
- (1)
- Stack (1)
- SPFA (0)
- CRT (1)
Common Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8893 Accepted Submission(s): 3578
Problem Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
Sample Input
abcfbc abfcab programming contest abcd mnp
Sample Output
4 2 0
Source
Recommend
Ignatius
呢个系DP既一种经典题型,叫LCS(Longest Common Subsequence)最长公共子序列,系允许吾连续,连续又系另外一种鸟。
首先就系要提到一种叫做最优子结构既性质,相当好用正斗既性质。
设X = <x1, x2, ........xm>, Xm-1 = <x1, x2, .........xm-1>
Y = <y1, y2, ........yn>, Yn-1 = <y1, y2, .........yn-1>
Z = <z1, z2, ........zk>, Zk-1 = <z1, z2, ........zk>
Z = <z1, z2, ........zk>, Zk-1 = <z1, z2, ........zk>
另外Z为X,Y既LCS,就可以引出如下性质:,
1、当xm = ym既时候, Zk-1为Xm-1同埋Yn-1既LCS。(因为zk就系xm(ym), 呢种情况Z = Zk-1 + 1)
2、当xm != ym既时候, Z就系 "Xm-1同Y” 或者 "X同Yn-1" 既LCS。(即系两种可能之间既最大值)
根据呢两个性质就可以即刻写出一个递归定义:
两个序列既LCS包含左两个序列前序既然LCS。
姐系甘,你要求XY既LCS,就首先要求出"Xm-1同 Yn-1"、 "Xm-1同Y” 或者 "X同Yn-1"既LCS。
写成递归式就系下面甘样:
设ts[i][j]储存Xi同Yi既LCS长度。
{ ts[i][j] = 0 i = 0 || j = 0 //注意呢度可以解决空集情况
ts[i][j] = { ts[i][j] = ts[i][j] xi = yi
{ ts[i][j] = Max(ts[i][j - 1], ts[i - 1][j]) xi != yi
但系如果字符串好大, 写递归好明显吾得吃,所以用二维数组递推,时间复杂度O(n*m)。
下面系代码:
4226991 | 2011-07-20 15:59:19 | Accepted | 1159 | 62MS | 24556K | 952 B | C++ | 10SGetEternal{(。)(。)}! |
#include <iostream> #include <string> using namespace std; #define MAXF(x, y) (x > y? x: y) string x, y; int lx, ly, **ts; void print(int *arr, int siz) { int i; for (i = 0; i < siz; i++) printf("%6d", arr[i]); putchar('\n'); } void init() { int i; lx = x.length(); ly = y.length(); ts = new int *[lx + 1]; for (i = 0; i < lx + 1; i++) { ts[i] = new int [ly + 1]; memset(ts[i], 0, sizeof(int) * (ly + 1)); #if 0 print(ts[i], ly + 1); #endif } } int dp() { int i, j; #if 0 printf("test = %d\n", MAXF(8, 7)); #endif for (i = 1; i <= lx; i++) for (j = 1; j <= ly; j++) if (x[i - 1] == y[j - 1]) ts[i][j] = ts[i - 1][j - 1] + 1; else ts[i][j] = MAXF(ts[i][j - 1], ts[i - 1][j]); return ts[lx][ly]; } int main() { while (cin >> x >> y) { #if 0 printf("%s %s\n", x.c_str(), y.c_str()); #endif init(); printf("%d\n", dp()); } return 0; }
搞掂{= =+}
发表评论
-
HDU 1370 Biorhythms
2011-08-03 10:27 1200Biorhythms Time Limit: 2000/10 ... -
HDU 1075 What Are You Talking About
2011-08-04 11:00 869What Are You Talking About Tim ... -
HDU 1058 Humble Numbers
2011-08-02 15:55 1227Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 822find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 1018Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 768box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 857Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 1031Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1212二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 1034Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 909Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 802Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1066分拆素数和 Time Limit: 1000/1000 MS ... -
ZOJ 3512 Financial Fraud .
2011-07-31 20:49 1293Financial Fraud Time Limit: 3 ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1130Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 691Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 605find the safest road Time Limi ... -
HDU 2553 N皇后问题 .
2011-07-31 20:20 706N皇后问题 Time Limit: 2000/1000 MS ... -
HDU 1392 Surround the Trees .
2011-07-31 20:19 805Surround the Trees Time Limit: ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 677开门人和关门人 Time Limit: 2000/1000 ...
相关推荐
杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...
HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-...
这个压缩文件包含的是作者个人提交并解决的ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)题目,这些题目来源于HDU的在线编程平台。 【描述】"杭电的一些acm题目,都是我自己一个一...
HDU-ACM课件.rar 是一个专门为编程竞赛爱好者准备的资源包,主要涵盖了ACM(国际大学生程序设计竞赛)中常见的算法知识。这个压缩包包含了一系列与算法相关的主题,旨在帮助初学者理解和掌握基础及进阶算法。下面将...
标题中的“算法-数塔(HDU-2084)”是指一个编程竞赛题目,源自杭州电子科技大学(HDU)的在线编程平台。在这个问题中,参赛者被要求解决一个名为“数塔”的算法挑战。数塔问题通常涉及到递归、深度优先搜索(DFS)...
标题中的"HDU-1535-.zip_多源点"表明这是一个关于解决 ACM (国际大学生程序设计竞赛)问题的程序代码包,问题编号为 HDU 1535,且该问题涉及到多源点的最短路径计算。描述中提到的"求多源点到单终点的最短路(反向...
标题中的“算术(HDU-6715)”很可能是指一个编程竞赛或在线教育平台上的一个问题或挑战,通常这类题目会涉及到算法和数学的应用。由于没有具体的标签信息,我们将根据题目标题和可能的内容来推测相关的IT知识点。 ...
《算法-确定比赛名次(HDU-1285)》 算法是计算机科学的基础,也是解决复杂问题的关键工具。在这个问题中,我们聚焦于一个具体的算法挑战——确定比赛名次,这个问题来源于HDU(杭州电子科技大学)的在线编程竞赛...
《最短路问题详解》 在计算机科学领域,最短路问题是一个经典的图论问题,其目标是寻找网络中两点间路径的最小成本。这个问题在众多应用中都有所体现,如交通规划、通信网络设计、社交网络分析等。...
数字图像处理是计算机科学和信息技术领域中的一种重要技术,涉及到图像处理、图像分析和图像识别等方面。下面是根据给定的文件信息生成的相关知识点: 1. 数字图像的定义和分类:数字图像是指使用数字信号表示的...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...