题目：  给定前N个自然数的一个乱序排列， 比如 3 1 2，  求能让其顺序排列的最小操作次数。其“操作”只有一种，即对任何一个子序列反序。   所以，312，需要操作两次  312-》321-》123。输出2.

输入4321 ，输出1.  


目前只想到一个比较费时间， 特别费空间的算法：

原始输入序列压入队列，同时记录操作次数为0。
while （队列非空）：
   弹出队列头和当前操作次数。
   两重循环遍历该当前序列的所有子序列：
       反序该子序列
       if（顺序了）：
           返回当前操作次数 + 1
           结束
       else：
           把（得到的新序列，当年操作次数+1）压入队列

有没有经济一点的办法？
--
FROM 81.157.216.*

感觉跟我上面的算法等价啊

我那个就是每次走一步， 走到了就退出， 没走到就要记录现场，然后继续。。。。。


【 在 cafitren 的大作中提到: 】
: 是的，但是你不需要显式地事先把图建起来，可以边算距离边加点。
: 最坏情况可能会相当于把这些节点都建了，但是平均情况应该只要建一小部分。
:
--
FROM 81.157.216.*

微软好像是只能反转前面的子序列， 不是任意子序列。

那样分之少好多。 时间空间都降了一阶

【 在 lengxinyi 的大作中提到: 】
: 这不就是微软的翻饼问题么
: 基本就动态规划、贪心、分支限界法几种
: 你这个算法如果能剪枝的话会稍快一点
: ...................
--
FROM 86.188.38.*

我没说先排1或6啊



【 在 Jangbi 的大作中提到: 】
: 嗯，这个就是找到的一个反例，证明不能先排1或者6
:
--
FROM 86.189.131.*