对于一套导弹拦截系统，它要不可以拦截上升序列，要不可以拦截下降序列，现在问最少需要多少套系统。
很自然的想到LIS算法，可惜在这里不能用，如果这样贪心的话
每套系统拦截最多的导弹和系统的数量最少没有什么直接联系，应该不会正确
而LIS中，最核心的思想在于能否将一个元素加入到序列中，只与这个序列目前的最后一个元素有关
这道题就用了这个关键的思想。
用up[k]和down[k]记录第k套上升（下降）系统目前所拦截的最后一个导弹
dfs(u,v,t)意味着已有u个上升，v个下降，正在处理第t个数
按理说，每拿到一个新的数字应该将它所有能放入的序列都放一遍的
但扩展节点时却存在一个贪心策略，大大节省了时间。
假设现在要把一个数放入一个上升序列，那么一定是所有能放入的上升序列中，最后一个元素最大的那一个。
其实想想也是，既然每个数字都要放到一个序列中，
对于上升序列，肯定是目前越小越有用，既然能放入大的里面，何必浪费一个小的呢
注意到其实up[i]按这种策略已经是排好序的了，所以只用找最先碰到的一个就行了
这样将深搜的树从一个多叉树变成了二叉树，时间效率提升很大。
#include<iostream>
using namespace std;
#define max(a,b) a>b?a:b
int n,res,a[60];
int up[60],down[60];
void dfs(int u,int v,int t)
{
if(u+v>=res)return;
if(t>n)
{
if(u+v<res)res=u+v;
return;
}//找到更好的结果
int i,tmp;
//UP
for(i=1;i<=u;i++)
if(up[i]<a[t]) break;
tmp=up[i];
up[i]=a[t];
dfs(max(i,u),v,t+1);
up[i]=tmp;
//DOWN
for(i=1;i<=v;i++)
if(down[i]>a[t]) break;
tmp=down[i];
down[i]=a[t];
dfs(u,max(i,v),t+1);
down[i]=tmp;
}
int main()
{
int i;
while(scanf("%d",&n) && n)
{
res=100;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
dfs(0,0,1);
printf("%d\n",res);
}
}