《震荡数组》题目分析

这道题是一道搜索题目，30!状态很多，需要一些搜索、剪支技巧才能AC。

首先震荡数组要求A[i]-A[i-1]，正负交替。我们不妨规定先正后负，计算一次最少交换次数；然后规定先负后正，再计算一次。

搜索可以用A*算法，减少扩展的状态。A*算法可以参考搜索三·启发式搜索

启发函数H有很多种设计。例如，每次交换A[i]和A[j]，会改变4个差值A[i]-A[i-1], A[i+1]-A[i], A[j]-A[j-1], A[j+1]-A[j]。所以 我们可以令H(S) = ceil(S中错误的差值 / 4)。 S是当前状态，所谓错误的差值是指本应是正的，当前是负的；或者本应是负的，但是 当前是正的的差值。

最优化剪支：如果当前状态的估计交换数(H函数估计)不少于当前已知的最优交换次数，就没有必要再搜索下去了。

除了A*搜索之外，还可以使用迭代加深的搜索策略。

BTW，本题之前通过的提交中，有些程序使用了特殊的剪支方法。我不太确定是不是100%正确的，但是也构造不出反例。如果大家有什>么高明的剪支策略欢迎在后面分享~