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:谁能简单说下这个题目的思路么?谢谢了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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator