题解：P10490 Missile Defence System

· · 题解

题目传送门。

博客食用更佳。

（有任何问题欢迎各位大佬指出交流 %%%。）

非常好的一道练习搜索的题。

分析题意

首先，这道题很明显是一道深搜加剪枝。

我们根据题意可知，对于一发导弹，我们有四种方案：

  1. 新建一个递增拦截装置。
  2. 新建一个递减拦截装置。
  3. 使用已有的递增拦截装置。
  4. 使用已有的递减拦截装置。

所以我们只需在 1 和 3 之间选一种，2 和 4 之间选一种 。

但如果直接爆搜，n\le50 的范围很容易会 boom 挂掉。

所以我们需要优化，对于一个搜索，我们的优化方式大多有这几种：

1.优化搜索顺序（如提前排序/倒置等，如小木棍 P1120，预处理从大到小排序，省好多时间）

2.排除等效冗杂（如小木棍 P1120，同等长度木棍只需判断一次即可）。

3.可行性剪枝（如贪心优化）。

4.最优性剪枝（如若搜索答案已经劣于现已知最优答案，果断回溯）。

5.记忆化搜索（把答案记录下来，避免重复减少时间)。

1.考虑可行性剪枝

再考虑可行性剪枝，可以用贪心的思想，（楼下 luobotianle 大佬 解释的非常好，简单易理解，这里就直接引用了。）

如果对于一个导弹，我们有两个递增装置都能够拦截它，那么基于贪心，我们一定会选择目前高度最高的一个去拦截它（因为低的那一个“更有潜力”）

如现在有两个递增装置，第一个依次拦截了高度为 2 5 8 的三枚导弹，第二个拦截了 6 7 的两枚导弹，那么如果又来了一发高度为 9 的导弹，那么用第一个拦截一定会比第二个更优。

递减装置同理。

2.考虑最优性剪枝

当目前答案已经大于已知最优答案时，直接回溯即可。

综上，AC_code 如下，要注意一些细节问题。

#include<bits/stdc++.h>
using namespace std;

#define int long long
int n,a[60],ans = 0x7fffffff;
vector<int> up,down; //分别记录递增序列的最大值和递减序列的最小值 

void dfs(int now)
{
    int x = up.size(),y = down.size();
    if(x+y>=ans) return; //最优性剪枝，解释参见上文 
    if(now>n) //搜索结束
    {
        ans = min(ans,x+y); 
        return;
    }
    for(int i = 0;i<x;i++)
    {
        if(up[i]<a[now]) 
        {
            int tmp = up[i]; 
            up[i] = a[now]; 
            dfs(now+1);
            up[i] = tmp; 
            break; //显然每次只会更新第一个值，第一个找到的值一定是可行的最大值  
        }
    }
    if(!x or (up[x-1]>=a[now])) //新建一个递增装置 
    {
        up.push_back(a[now]); 
        dfs(now+1); 
        up.pop_back();  
    }
    for(int i = 0;i<y;i++) //遍历每一个递减序列 
    {
        if(down[i]>a[now])
        {
            int tmp = down[i]; 
            down[i] = a[now];
            dfs(now+1);
            down[i] = tmp;
            break;
        }
    }
    if(!y or (down[y-1]<=a[now])) //新建一个递减装置 
    {
        down.push_back(a[now]);
        dfs(now+1);
        down.pop_back();
    }
} 

signed main()
{
    while(cin>>n && n) 
    {
        if(n==0) break; 
        ans = 0x7fffffff;
        for(int i = 1;i<=n;i++) cin>>a[i]; 
        up.clear(), down.clear(); //多测一定要记得初始化！！！ 
        dfs(1); 
        cout<<ans<<endl;
    }
    return 0;
}

第一次写题解，有问题的地方还请指出，多多包涵。