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 morris1028 at 2013-10-02 20:29:03 on Problem 2052
In Reply To:谁能简单说下这个题目的思路么?谢谢了 Posted by:kansas at 2007-06-04 21:05:36
相當於是 TSP 的狀態壓縮方式,O(2^16*16)。
只怕要處理單一組自繞資訊(縮繞幾圈的結果)。
環狀處理相當重要,處理的時候必然討論是一條鍊狀,而為了方便繞回來的檢查,
TSP 考慮時,從最長資訊開始討論,其後保證一定繞得回來。
如何保證每次連接最佳,最後一定會最佳?
考慮串接時,每組資訊的起頭位置必然呈現有序的,
而且必然會在重疊後仍多出一小段,如果被包含前一段中,
直接在預處理篩掉這種無須考慮的資訊。
由於每組資訊可能會存在順逆時針 狀態 O(2^16*16*2)。

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