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

Re:这是经典的错误,正向最小的方案不一定满足题意,详细反例见内。

Posted by antoniowyn at 2008-08-21 14:15:46 on Problem 1239
In Reply To:不是二次dp ? 一次正向得到最小,一次反向是前面的最大,为什么就wa了? Posted by:achilles at 2005-09-09 09:58:00
123455
正向最小:
1,2,3,4,55
再求反向最大,还是1,2,3,4,55
但正解是:12,34,55
原因:虽然4是1234中最好后缀,但由于最后的后缀是55,因此1234中4和34这两种后缀都是可以接受的,但是后缀为34可以得到更好的开头(12),而后缀为4不行。

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