题目描述
为了对抗附近恶意国家的威胁,R国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如,一套系统先后拦截了高度为3和高度为4的两发导弹,那么接下来该系统就只能拦截高度大于4的导弹。
给定即将袭来的一系列导弹的高度,请你求出至少需要多少套防御系统,就可以将它们全部击落。
使用DFS求最优解的两种方法: (1) 全局变量更新 (2) 迭代加深
算法1:全局变量更新最优解 DFS
时间复杂度:指数复杂度
C++ 代码
#include<iostream>
using namespace std;
const int N=55;
int q[N];
int down[N],up[N];
int res;
int n;
void dfs(int u,int su,int sd)
{
if(su+sd>=res)return;
if(u==n){
res=su+sd;
return;
}
//情况1:当该数字插入到上升序列中
//上升序列结尾的数组是单调上升的,可以使用二分进行查找
int k=0;
while(k<su && up[k]>q[u])k++;
//结尾的数组可以更新,不用开新的上升序列
if(k<su){
int t=up[k];//为了恢复现场
up[k]=q[u];
dfs(u+1,su,sd);
up[k]=t;
}
//结尾的数组不可以更新,需要开新的上升序列
else {
up[k]=q[u];
dfs(u+1,su+1,sd);
}
//情况2:当改数字插入到下降序列中
//与上升序列的情况基本相同
k=0;
while(k<sd && down[k]<q[u])k++;
if(k<sd){
int t=down[k];
down[k]=q[u];
dfs(u+1,su,sd);
down[k]=t;
}
else {
down[k]=q[u];
dfs(u+1,su,sd+1);
}
}
int main()
{
while(cin>>n,n){
for(int i=0;i<n;i++)scanf("%d",&q[i]);
res=n;
dfs(0,0,0);
cout<<res<<endl;
}
return 0;
}
算法2:迭代加深 DFS
#include<iostream>
#include<cstring>
using namespace std;
const int N=55;
int up[N],down[N]; //分别存储上升序列和下降序列的末尾元素
int h[N];
int n;
bool dfs(int depth,int u,int su,int sd)
{
if(su+sd>depth)return false;
if(u==n)return true;
//上升
int k=0;
while(k<su && up[k]>=h[u])k++;
if(k<su){
int t=up[k];
up[k]=h[u];
if(dfs(depth,u+1,su,sd))return true;
up[k]=t;
}
else{
up[k]=h[u];
if(dfs(depth,u+1,su+1,sd))return true;
}
k=0;
while(k<sd && down[k]<=h[u])k++;
if(k<sd){
int t=down[k];
down[k]=h[u];
if(dfs(depth,u+1,su,sd))return true;
down[k]=t;
}
else{
down[k]=h[u];
if(dfs(depth,u+1,su,sd+1))return true;
}
return false;
}
int main()
{
while(cin>>n,n){
for(int i=0;i<n;i++)scanf("%d",&h[i]);
int depth=0;
while(!dfs(depth,0,0,0))depth++;
cout<<depth<<endl;
}
return 0;
}