导弹防御系统【dfs】主题链接
引言(请忽略) )今天是阳光明媚的大树ACM集训日。 而且，数据结构太难了，怎么也学不会。 然后，只能无力地复习以前的问题。 我记得以前SDUT路线上有最低监听系统的问题。 它很贪婪，我个人认为最长的上升子程序的想法与之相似。 首先分析这个问题，引入这个最低监听系统的问题和代码：
最少拦截系统
Description
一旦提取了问题，就会有几枚导弹飞过来，需要用炮弹系统依次迎击。 那第一发炮弹可以到达任意高度，但以后任何炮弹都不能超过前面导弹的高度。 例如，如果飞来的导弹高于迄今为止所有的导弹，就只能增加一个拦截系统。 求监听系统的数量
输入
输入：导弹的总个数(正整数)，导弹从这里飞来的高度)雷达给定的高度数据是30000以下的正整数，用空格隔开)。
Output
应对所有导弹的拦截，最少必须装备多少套这种导弹拦截系统？
桑普
输入
8 389 207 155 300 299 170 158 65
Output
2
# include stdio.h # include string.hinta，I； //用于储存导弹的高度int b[100000]； //用于保存拦截系统能够拦截的高度的int main () intn，cnt； //n表示全部导弹的个数，cnt表示拦截系统的个数while(Scanf('%d '，n )！=EOF () memset ) b，0，sizeof(b ) b )； //b为了保存监听系统可以监听到的最大高度cnt=1，for(I=0； in； I ) Scanf('%d '，a )； if(I==0) b[0]=a； int j； for(j=0； JNT； j(//每次将b的值置换为较小的高度(if ) {{b[j]=a ) } /监听系统如果可以监听的话就进行监听) b[j]=a； 黑； }if(j==CNT )//如果监听系统不能全部监听，就只能再利用另一个监听系统({b[cnt ]=a； }printf('%dn '，cnt )； }return 0； }这个问题是在现有的拦截系统中寻找的问题。 因为各拦截系统会判断导弹飞来时能否拦截，并更新各拦截系统能拦截的最大高度。 输出最后计数的cnt就可以了，但是因为是贪婪战略的主题，所以难度还可以。
但是今天这个主题真的让我很难破坏这棵明亮的大树。
187 .导弹防御系统描述
为了对抗邻国恶意的国家威胁，r国更新了导弹防御系统。
一系列防御系统的导弹拦截高度一直为严格单调 上升或一直为严格单调 下降。
例如，如果一个系统相继拦截了2枚高度为3和高度为4的导弹，则接下来该系统只能拦截大于高度4的导弹。
请决定即将来袭的一系列导弹的高度，并求出至少需要多少套防御系统。 可以把它们全部击落。
输入格式
输入一组多个测试用例。
对于每个测试用例，第一行包含整数n，表示飞来导弹的数量。
第二行包含n个不同的整数，表示每个导弹的高度。
如果输入测试用例n=0，则输入结束，不需要处理用例。
输出格式
对于每个测试用例，输出一个整数，该整数占一行，表示所需的防御系统数量。
数据范围
1n50
输入样例
53 5 2 4 10 输出样例
2 样例解释
要拿出样品，至少需要两个防御系统。
一枚击落高度为3、4的导弹，另一枚击落高度为5、2、1的导弹。
题解这个问题很多网络大人物的解析，我作为开朗的大树也不是很深的理解，所以可能会有误会。 这里只是记录自己的学习过程。
首先看问题就知道，某种导弹既可以上升也可以下降，所以不能像前面的问题那样只记录多少组上升子程序的问题。
我想到的是列举一下去暴搜；
一枚导弹的高度应该是递增序列还是递减序列，以及应该在哪个递增序列或递减序列中是一个核心问题。
这个问题要求时间复杂，在搜索过程中必须经常考虑优化，在适当的地方修剪树枝。
搜索
第一个搜索可能是BFS。 宽度优先。 虽然网络上有使用这种方法的大人物，但是介于内存存储器之间的一些写法我不太清楚，所以就不多说了。 二是DFS。 是我采用的方法。 修剪树枝的过程确实很容易写，所以我只能考虑这个方法。 然后，可以采用声明全局最小值记录和反复深入检索两种想法。 时间的复杂性都是n*2^n，所以我用前者写这个代码。
因为明亮的大树也不怎么会，可能注释写的比较繁琐，代码如下：
#include <iostream>using namespace std;const int N = 100;int n;int q[N];//q：依次飞来的导弹; int up[N],down[N];int ans; // 记录全局最小变量;void dfs(int x,int su,int sd) // x:当前枚举到哪个数,su:上升子序列的个数,sd:下降子序列的个数{ if(su + sd >= ans) return ; // 剪枝---此时不可能再更新了，return if(x==n) // 递归结束 { ans = su + sd;//上升子序列和下降子序列个数和为答案 return ; } // 情况1：将当前数放到上升子序列中 int k =0;//k用来遍历当前所有上升子序列的末尾值 while(k < su && up[k] >= q[x]) k++; // 因为序列下标是从0开始的，所以是< int t=up[k]; // 为后边回溯标记当前遍历; up[k] = q[x];//如果q[u]比末尾值大，则更新up数组； if(k < su) dfs(x+1,su,sd); // 如果被更新---即不用另开一个上升子序列m//如果k>=su说明q[当前]小于所有上升子序列 else dfs(x+1,su+1,sd);//则su+1 （增加一个系统），继续深搜 up[k] = t; // 回溯之前的状态 //情况2与上同理； // 情况2：将当前数放到下降子序列中 k = 0; while(k < sd && down[k] <= q[x]) k ++; t = down[k]; down[k] = q[x]; if(k < sd) dfs(x+1,su,sd); else dfs(x+1,su,sd+1); down[k] = t;}int main(){ while(cin >> n&& n) { for(int i=0;i<n;i++) cin >> q[i]; ans=n; dfs(0,0,0); cout<<ans<<endl; } return 0;}这个题我觉得对我来说是挺难的，也借鉴了许多网上大佬的思路，仅用来记录自己的学习过程吧。
新手上路，多多包涵。