Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贪心思路 (没有完全证明出来,感觉正确的概率很大,而且A了):从辅助stack个数无限的贪心算法开始,然后设计辅助stack个数为2的贪心如果stack很多, 每一步操作只有两种可能 1. 把所有其他的frame都移除,只剩目标frame 2. 通过一次移动把目标frame移出来到一个空闲的stack上, 然后从这个stack上开始新的递归 (移出部分frame后再把目标frame移出不会更优) 现在只有2个多余stack,当需要空闲stack的时候而没有空闲的stack的时候,总是可以通过“一次”移动把某一个不包含目标frame的stack清理成空闲状态。 也就是说3个stack: 1. 包含目标frame的stack 2. 垃圾stack 3. 临时stack/空闲stack,可以通过一次操作把该stack的所有frame移动到垃圾stack上成为空闲stack 正确性没有完全证明出来,但是AC了,^_^ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator