1.迭代加深+贪心

1. 迭代加深+贪心 O(n*2^n)

#include <cstdio>
const int N = 66;

using namespace std;

int n, ans, a[N], up[N], down[N];
//ans枚举depth
//up[i]和down[i]分别储存第i个上升子序列和下降子序列的最后一个数

bool dfs (int dep, int cur, int uu, int dd)
//cur为当前需要拦截的导弹的编号
//uu和dd分别是当前上升子序列和下降子序列的个数
{
	if (uu + dd > dep) return 0;  //超出深度就返回
	if (cur == n) return 1;   //数组从0开始使用, 所以到n就返回

     //接下来分别试探当前导弹能否被已知系统拦截
     //对于上升子序列而言（下降子序列类似），将当前数接在最大的数后面，一定不会比接在其他数列后面更差。
     //这是因为处理完当前数后，一定会出现一个以当前数结尾的子序列，这是固定不变的，那么此时其他子序列的末尾数越小越好。
     //按照这种贪心思路，up[]和down[]一定是单调的，因此在遍历时找到第一个满足的序列后就可以直接break了
	
	bool ok = 0;//记录是否成功
	for (int i = 1; i <= uu; i++)
	{
		if (up[i] < a[cur])
		{
			int b = up[i]; //备份当前up[i]
			up[i] = a[cur];
			if (dfs(dep, cur+1, uu, dd)) return 1; //dfs下一层
			ok = 1;
			up[i] = b; //还原
			break;
		}
	}
    if (!ok) {
        up[uu + 1] = a[cur];
        if (dfs(dep, cur + 1, uu + 1, dd))
            return 1;
    }
	
	ok = 0; //下降的进行同上
	for (int i = 1; i <= dd; i++)
	{
		if (down[i] > a[cur])
		{
			int b = down[i];
			down[i] = a[cur];
			if (dfs(dep, cur+1, uu, dd)) return 1;
			ok = 1;
			down[i] = b;
			break;
		}
	}
	if (!ok)
	{
		down[dd+1] = a[cur];
		if (dfs(dep, cur+1, uu, dd+1)) return 1; 
	}
	return 0;
}

int main()
{
	while (scanf("%d",&n) && n)
	{
		ans = 0;
		for (int i = 0; i < n; i++) scanf("%d",&a[i]);
		while(!dfs(ans,0,0,0)) ans++; //迭代加深
		printf("%d\n",ans);
	}
	return 0;
}