题目链接：https://www.acwing.com/problem/content/description/189/
为了对抗附近恶意国家的威胁， 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如，一套系统先后拦截了高度为 和高度为 的两发导弹，那么接下来该系统就只能拦截高度大于 的导弹。
给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。
从yxc老师的分析中，可以看出。我们当前数既可以存在于上升子序列数组中充当元素，也可以存在于下降子序列中充当元素。所以我们既需要带入up中去寻找其他可以，又需要去代入到down中寻找其他可能，你们就需要dfs回溯这么一个过程来求出结果。
code:
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int a[55];
int up[55],down[55];
int ans;
int n;
void dfs(int cur,int sup,int sdn)
{
if(sup+sdn-2>=ans) return;
if(cur==n+1){
ans = sup+sdn-2;
return ;
}
int k=1;
while(k<sup && up[k]>=a[cur]) k++;//其实就是贪心思想查找a[cur]的位置
int t = up[k];
up[k] = a[cur];//尝试放入
if(k<sup) dfs(cur+1,sup,sdn);//不是一个新的值
else dfs(cur+1,sup+1,sdn);//是一个新的情况
up[k] = t;//再把原来的数放回来，因为要求出所有的情况
k=1;
while(k<sdn && down[k]<=a[cur]) k++;
t = down[k];
down[k] = a[cur];
if(k<sdn) dfs(cur+1,sup,sdn);
else dfs(cur+1,sup,sdn+1);
down[k] = t;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
while(cin>>n&&n)
{
for(int i=1;i<=n;i++) cin>>a[i];
ans = n;
dfs(1,1,1);
cout<<ans<<endl;
}
}
我们来可以迭代加深这种做法。上一个做法中，我们说到需要考虑到当前数放在了不同的序列中。我们要求得的结果是两个序列之和的最小值，那么我们可以从1来看，代码中为0也可以因为不存在没有数。然后我们来看看这两个序列的和是否可以在sept内完成，如果已经足以走到了n-1之后的n，意味着包含了所有的数了，那么返回true。我们可以看到在代码中任何一个位置返回了true将一直为true。迭代加深更像是去带着结果（可能不正确）去搜索它是否正确。在枝叶较少的情况下，感觉可能会更好一点的选择。
code：
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int a[60],up[60],down[60],n;
bool dfs(int step,int u,int su,int sd){
if(su+sd>step) return false;//上升和下降的情况大于总要求
if(u==n) return true;//如果能够包含所有的数
//将当前数放入到上升子序列的合理位置
bool flag = false;
for(int i=1;i<=su;i++)
if(up[i]<a[u]){
int t = up[i];
up[i] = a[u];
if(dfs(step,u+1,su,sd)) return true;
up[i] = t;
flag = true;
break;
}
if(!flag){
up[su+1] = a[u];
if(dfs(step,u+1,su+1,sd)) return true;
}
//将当前数放入到下降子序列的合理位置
flag = false;
for(int i=1;i<=sd;i++)
if(down[i]>a[u]){
int t = down[i];
down[i] = a[u];
if(dfs(step,u+1,su,sd)) return true;
down[i] = t;
flag = true;
break;
}
if(!flag){
down[sd+1] = a[u];
if(dfs(step,u+1,su,sd+1)) return true;
}
return false;
}
int main()
{
while(cin>>n&&n){
for(int i=0;i<n;i++) cin>>a[i];
int step = 0;
while(!dfs(step,0,0,0)) step++;
cout<<step<<endl;
}
}