自动搬运

查看原文

来自洛谷，原作者为

	Atserckcn 愿你的刀仍然锋利

搬运于2025-08-24 22:58:30，当前版本为作者最后更新于2024-06-18 22:47:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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 记录