[問題] ICPC 6036 Stacking Plates
看板Prob_Solve (計算數學 Problem Solving)作者mob5566 (ChengShih)時間10年前 (2014/06/04 00:12)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/1
題目的意思是
給定n個stack，每個stack中會有hi個盤子
stack中的盤子必須滿足由上到下盤子的大小非遞減排序
(類似河內塔)
對於兩種操作:
1. 分離: 將一個stack分成兩個stack
2. 合併: 將一stack放置到另一stack上，且滿足
由上到下非遞減排序
問最少能使用多少個操作將所有stack合併成1個stack?
目前的想法:
若盤子的大小唯一，就非常簡單，只需要排序後計算有幾個partition
但現在有可能有相同大小的盤子，就必須考慮相同大小盤子間排序的
情況
有看到有人說要用DP，但我不知道如何建立狀態轉移方程QQ
不知道有沒有能幫我解答，感謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.227.157.102
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1401811968.A.285.html
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
