[问题] 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