PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Prob_Solve
Re: [问题] UVA 120
楼主:
coconutman
(被椰子砸到)
2012-11-29 20:57:39
这题题意没有要求最佳解。
但如果要求最佳解的话,不晓得有没有人有办法解的出来呢?
: : 我想用递回的方法做,三个步骤
: : 1.若最上面的元素最大 不反转
: : 2.若最大元素不在最上面 在最下面 则翻转一次
: : 3.若最大元素不在最上面 也不在最下面 则翻转两次 先翻到最下面再翻到最上面
EX.
若用上上篇的步骤的话:
1243 -> 4213 -> 3124 -> 2134 -> 1234
但最佳解可为:
1243 -> 3421 -> 4321 -> 1234
数列长度限制在 30 以内。
作者:
LPH66
(-6.2598534e+18f)
2011-01-29 22:01:00
http://en.wikipedia.org/wiki/Pancake_sorting
这里好像有提到一些研究结果中间一段应该是说这个问题是 NP-hard
楼主:
coconutman
(被椰子砸到)
2011-01-29 22:31:00
wow~谢谢你!!原来已经有论文证明是是NP-hard!
继续阅读
Fw: [讨论] 参与 Codeforces 解题入门教学
changyuheng
[问题] DP
wsx02
Re: [问题] 红黑树, 中位数
eieio
[问题] 红黑树, 中位数
wsx02
Re: [问题] 散开 间距 的证明
seanwu
[问题] Dijkstra
wsx02
[问题] 散开 间距 的证明
Arton0306
[问题] 急难救助 哭哭
sandy780512
Re: [问题] Turbo 版老鼠走迷宫..
bleed1979
Re: [问题] Turbo 版老鼠走迷宫..
yauhh
Links
booklink
Contact Us: admin [ a t ] ucptt.com