Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

写个证明

Posted by asanasdake at 2007-07-03 17:47:32 on Problem 1989
证明子序列长度为至少是n当且仅当序列是这样的()()...()[],一个()是一次1..m都出现的序列,共n个。
必要性。数学归纳法。n>=1是,序列显然是()[],假设n>=k是,序列是k个()+[],如果n>=k+1,取第k个()的最后一个素,这个元素在长度为k的某个子序列中一定会用到,如果用不到就把它放到[]中去,这样做第k个()仍然是一次1..m都出现的序列,再取前一个元素,由归纳假设保证第k个()中一定有一个元素满足要求,由于n>=k+1,所以在这个元素之后必然会出现1..m的所有元素一次,所以[]=()[]'
充分性。太显然了,没什么证的。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator