[問題] ICPC 6036 Stacking Plates

作者: mob5566 (ChengShih)   2014-06-04 00:12:46
題目的意思是
給定n個stack,每個stack中會有hi個盤子
stack中的盤子必須滿足由上到下盤子的大小非遞減排序
(類似河內塔)
對於兩種操作:
1. 分離: 將一個stack分成兩個stack
2. 合併: 將一stack放置到另一stack上,且滿足
由上到下非遞減排序
問最少能使用多少個操作將所有stack合併成1個stack?
目前的想法:
若盤子的大小唯一,就非常簡單,只需要排序後計算有幾個partition
但現在有可能有相同大小的盤子,就必須考慮相同大小盤子間排序的
情況
有看到有人說要用DP,但我不知道如何建立狀態轉移方程QQ
不知道有沒有能幫我解答,感謝!

Links booklink

Contact Us: admin [ a t ] ucptt.com