Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Re:求出两个串的公共子序列长度lcs，然后用最长串的长度减去lcs，即是结果。

Posted by hitwh120410318 at 2013-04-14 20:28:42 on Problem 3356
In Reply To:求出两个串的公共子序列长度lcs，然后用最长串的长度减去lcs，即是结果。 Posted by:ecjtuzxg at 2008-06-28 08:53:19

这方法对滴~ 本人分析原因：

假设 xi,xj是公共子序列中的两个数
则在s1中，xi到xj之间的任意一个数必定不在（s2中xi到xj之间的数）中出现，因为如果出现，则不是最长公共子序列~

于是乎~ 不一样的数该补的补~该删的删~该变得变 操作数和这些数的个数一样。
所以“求出两个串的公共子序列长度lcs，然后用 最长串的长度减去lcs，即是结果。”
是对滴~~

Followed by:

Re:求出两个串的公共子序列长度lcs，然后用最长串的长度减去lcs，即是结果。 (14) hitwh120410318 2013-04-14 20:43:52

Post your reply here:

Home Page Go Back To top

Re:求出两个串的公共子序列长度lcs，然后用 最长串的长度减去lcs，即是结果。

Re:求出两个串的公共子序列长度lcs，然后用最长串的长度减去lcs，即是结果。