Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贪心思路 (没有完全证明出来,感觉正确的概率很大,而且A了):从辅助stack个数无限的贪心算法开始,然后设计辅助stack个数为2的贪心

Posted by lddlinan at 2020-08-06 13:00:00 on Problem 1232
如果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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator