竹園論壇

標題: 1119 - 複雜之河內塔問題 [打印本頁]

作者: domen111 時間: 2015-2-23 11:50
標題: 1119 - 複雜之河內塔問題
本帖最後由 domen111 於 2015-2-23 12:01 編輯

題目:: http://tioj.ck.tp.edu.tw/problems/1119
AC:: http://tioj.ck.tp.edu.tw/submissions/9952

我第一個AC這題，當然就是TopCoder囉! 網路上完全查不到這題的任何資訊

題意:
把河內塔問題複雜化，可能會有多個相同大小的圓盤，儘管有些圓盤大小相同但搬移完成後順序還是不能改變，但過程中大小相同的圓盤順序可以不同。

題解:
DP!
一般的河內塔問題可以用DP解，這題也能用DP解，只不過狀態和轉移較複雜了一點

DP狀態較特別的一點是多了一個j，代表是否反轉
反轉的定義是: 相同大小的圓盤順序相反

Code:

歡迎光臨竹園論壇 (http://forum.tfcis.org/)