作者coconutman (被椰子砸到)
站内Prob_Solve
标题Re: [问题] UVA 120
时间Thu Nov 29 20:57:39 2012
这题题意没有要求最佳解。
但如果要求最佳解的话，不晓得有没有人有办法解的出来呢？
: : 我想用递回的方法做，三个步骤
: : 1.若最上面的元素最大 不反转
: : 2.若最大元素不在最上面 在最下面 则翻转一次
: : 3.若最大元素不在最上面 也不在最下面 则翻转两次 先翻到最下面再翻到最上面
EX.
若用上上篇的步骤的话：
1243 -> 4213 -> 3124 -> 2134 -> 1234
但最佳解可为:
1243 -> 3421 -> 4321 -> 1234
数列长度限制在 30 以内。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 1.160.29.250
※ 编辑: coconutman 来自: 1.160.29.250 (11/29 20:59)
※ 编辑: coconutman 来自: 1.160.29.250 (11/29 20:59)
2F：→ LPH66:这里好像有提到一些研究结果 11/29 22:01
3F：→ LPH66:中间一段应该是说这个问题是 NP-hard 11/29 22:03
4F：→ coconutman:wow~谢谢你！！原来已经有论文证明是是NP-hard！ 11/29 22:31