POJ - 3700 Missile Defence System（DFS,迭代加深,剪枝,贪心）_综合

POJ - 3700 Missile Defence System

(DFS,迭代加深,剪枝,贪心) $O(n2^n)$
为了能遍历所有情况，我们首先考虑搜索顺序是什么。

搜索顺序分为两个阶段：

从前往后枚举每颗导弹属于某个上升子序列，还是下降子序列；
如果属于上升子序列，则枚举属于哪个上升子序列（包括新开一个上升子序列）；如果属于下降子序列，可以类似处理。

分别记录当前每个上升子序列的末尾数up[]，和下降子序列的末尾数down[]。这样在枚举时可以快速判断当前数是否可以接在某个序列的后面。

这里是记录每个子序列末尾的数；
上一题是记录每种长度的子序列的末尾最小值。

此时搜索空间仍然很大，因此该如何剪枝呢？

对于第二阶段的枚举，我们可以仿照上一题的贪心方式，对于上升子序列而言，我们将当前数接在最大的数后面，一定不会比接在其他数列后面更差。
这是因为处理完当前数后，一定出现一个以当前数结尾的子序列，这是固定不变的，那么此时其他子序列的末尾数越小越好。

注意到按照这种贪心思路，up[]数组和down[]数组一定是单调的，因此在遍历时找到第一个满足的序列后就可以直接break了。

最后还需要考虑如何求最小值。因为DFS和BFS不同，第一次搜索到的节点，不一定是步数最短的节点，所以需要进行额外处理。
一般有两种处理方式：

记录全局最小值，不断更新；
迭代加深。一般平均答案深度较低时可以采用这种方式。

时间复杂度

每个数在第一搜索阶段有两种选择，在第二搜索阶段只有一种选择，但遍历up[]和down[]数组需要 $O (n)$ 的计算量，因此总时间复杂度是 $O(n2^n)$

#include<stdio.h>
const int N = 60;
int n,h[N],up[N],down[N];bool dfs(int depth,int u,int su,int sd)
{
    if(su+sd>depth) return false;// 如果上升序列个数 + 下降序列个数 > 总个数是上限，则回溯if(u==n) return true;bool flag=false;// 枚举放到上升子序列中的情况for(int i=1;i<=su;i++)if(up[i]<h[u]){
    int t=up[i];up[i]=h[u];if(dfs(depth,u+1,su,sd)) return true;up[i]=t;flag=true;break;  // 注意由上述证明的贪心原理，只要找到第一个可以放的序列，就可以结束循环了}if(!flag)  // 如果不能放到任意一个序列后面，则单开一个新的序列{
    up[su+1]=h[u];if(dfs(depth,u+1,su+1,sd)) return true;}flag=false;// 枚举放到下降子序列中的情况for (int i=1;i<=sd;i++)if(down[i]>h[u]){
    int t=down[i];down[i]=h[u];if(dfs(depth,u+1,su,sd)) return true;down[i]=t;flag=true;break;  // 注意由上述证明的贪心原理，只要找到第一个可以放的序列，就可以结束循环了}if(!flag) // 如果不能放到任意一个序列后面，则单开一个新的序列{
    down[sd+1]=h[u];if(dfs(depth,u+1,su,sd+1)) return true;}return false;
}int main()
{
    while(scanf("%d",&n)&&n){
    for(int i=0;i<n;i++) scanf("%d",&h[i]);int depth=0;while(!dfs(depth,0,0,0)) depth++;// 迭代加深搜索printf("%d\n",depth);}return 0;
}