查看: 1049|回復: 0

[TIOJ] 1119 - 複雜之河內塔問題

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2015-2-23 11:50:42 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 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:
    遊客,本帖隱藏的內容需要積分高於 10 才可瀏覽,您當前積分為 0
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表