题解：P10490 Missile Defence System

· · 题解

P10490 Missile Defence System 题解

题目简述：

给定共 n 个导弹，每种拦截系统可以拦截上升或下降的导弹，求共需要几套系统。

思路简述：

因为导弹来临是按照顺序，而非高度，所以我们绝对不能用 sort（显而易见）。

那么我们不妨将每个导弹分个类：

1、可以用某个上升拦截系统拦截。

2、可以用某个下降拦截系统拦截。

3、需要新建一个上升拦截系统拦截。

4、需要新建一个下降拦截系统拦截。

考虑其中 1 跟 2，3 跟 4 是相互矛盾的，所以我们可以剪枝优化。

剪枝代码：

int upsize=up.size();
int downsize=down.size();
if(upsize+downsize>=ans) return;//这种情况已经超过或赶上之前我的最优方案了，我还留你干嘛
if(now>n)//全部拦截后
{
    ans=min(ans,upsize+downsize);//上升下降的总套数
//  printf("over ans:%d\n",ans);
    return;
}

AC CODE：

思路上文讲述得已经很清楚了，还不懂的可看注释。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
int n,ans;
int a[MAXN];
vector<int> up,down;//up存上升系统，down存下降系统
void dfs(int now)//现在正在拦截第now个导弹
{
    int upsize=up.size();//注意：千万不要把它俩定义成全局变量！！血泪教训，调了1小时
    int downsize=down.size();//注意：千万不要把它俩定义成全局变量！！血泪教训，调了1小时
    if(upsize+downsize>=ans) return;//上述剪枝
    if(now>n)
    {
        ans=min(ans,upsize+downsize);//上述剪枝
//      printf("over ans:%d\n",ans);
        return;
    }
    for(int i=0;i<upsize;i++)//开始枚举每个上升系统
    {
        if(up[i]<a[now])//可以拦截
        {
            int t=up[i];//t也不可以定义为全局变量！！
            //dfs回溯备份
            up[i]=a[now];
            dfs(now+1);//继续拦截下一个
            up[i]=t;
            break;
        }
    }
    if(upsize==0||up[upsize-1]>=a[now])//判断，是否需要新开一个上升系统
    {
        up.push_back(a[now]);
        dfs(now+1);
        up.pop_back();
    }
    //同上，ctrl C,ctrl V
    //说实话，我因为复制完漏了更改名字而调了半天，太蒻了
    for(int i=0;i<downsize;i++)
    {
        if(down[i]>a[now])
        {
            int t=down[i];
            down[i]=a[now];
            dfs(now+1);
            down[i]=t;
            break;
        }
    }
    if(downsize==0||down[downsize-1]<=a[now])
    {
        down.push_back(a[now]);
        dfs(now+1);
        down.pop_back();
    }
    return;
}
int main(){
    while (true)
    {
        scanf("%d",&n);
        if(n==0) break;//虽然题目没说，但由样例可知，n=0时结束
        up.clear();
        down.clear();
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        ans=0x7fffffff;//无穷大
        dfs(1);
        printf("%d\n",ans);
    }
    return 0;
}

AC 记录