拦截导弹（acwing.1010）
【题意】：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
【分析】：第一个输出直接LIS就行，对于第二个问要考虑贪心思想，考虑一个拦截系统，起最后一个的高度肯定越大越有利于后面的元素增加进来，所需要的系统肯定就越少。所以用一个g数组来维护其最小元素的最大值，元素的个数就是最终所需的最少的拦截系统的个数。
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int maxn=1e3+10;
int arr[maxn],t,dp[maxn];
int g[maxn];
int main()
{
int tot=0;
while (~scanf("%d",&t)){
arr[++tot]=t;
}
int ans=0;
for(int i=1;i<=tot;++i){
dp[i]=1;
for(int j=1;j<i;++j){
if(arr[j]>=arr[i]) dp[i]=max(dp[i],dp[j]+1);
ans=max(ans,dp[i]);
}
}
printf("%d
",ans);
ans=0;
//贪心,g数组维护最大的最短长度
for(int i=1;i<=tot;++i){
int k=1;
while (k<=ans&&g[k]<arr[i]) k++;
g[k]=arr[i];
if(k>ans) ans++;
}
printf("%d
",ans);
system("pause");
}
导弹防御系统（acwing.187）
【题意】：为了对抗附近恶意国家的威胁，R国更新了他们的导弹防御系统。一套防御系统的导弹拦截高度要么一直上升要么一直下降。例如，一套系统先后拦截了高度为3和高度为4的两发导弹，那么接下来该系统就只能拦截高度大于4的导弹。给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。
样例输入（n<=50）：
5
3 5 2 4 1
0
样例输出：
2
【分析】：对于每一个元素，它只有两种状态：属于上升拦截系统或者属于下降拦截系统，所以用一个 dfs 既可以枚举所有状态；直接 dfs 其时间复杂度肯定超时（2^50）,所以随便剪剪枝就好了。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=55;
int arr[maxn],n,up[maxn],down[maxn];
int ans;
void dfs(int u,int d,int num) //u为上升系统的个数,d为下降系统的个数,num为数组中低级个数
{
if(u+d>=ans) return;
if(num==n){
ans=u+d;
return;
}
int k=1;
//属于上升子序列
while (up[k]>=arr[num]&&k<=u) k++;
int t=up[k];
up[k]=arr[num];
if(k>u) dfs(u+1,d,num+1);
else dfs(u,d,num+1);
up[k]=t;
k=1;
//属于下降子序列
while (down[k]<=arr[num]&&k<=d) k++;
t=down[k];
down[k]=arr[num];
if(k>d) dfs(u,d+1,num+1);
else dfs(u,d,num+1);
down[k]=t;
k=1;
}
int main()
{
while(~scanf("%d",&n)&&n){
for(int i=1;i<=n;++i) scanf("%d",&arr[i]);
memset(up,0,sizeof(up));
memset(down,0,sizeof(down));
ans=n;
dfs(0,0,1);
printf("%d
",ans);
}
//system("pause");
}