2.迭代加深+二分

2.迭代加深+二分 O(logn*2^n)

#include <cstdio>
const int N = 66;

using namespace std;

int n, ans, a[N], up[N], down[N];


bool dfs (int dep, int cur, int uu, int dd)
{
	if (uu + dd > dep) return 0;
	if (cur == n) return 1;

    //从这里开始不同，先判断是否可接到已有系统后
	if (!uu || up[uu]>=a[cur])
	{   
        //不可以就新加一个
		up[uu+1] = a[cur];
		if (dfs(dep, cur+1, uu+1, dd)) return 1;
	}
	else {
        //二分找最合适的地方（贪心）
		int l=1, r=uu;
		while (l < r)
		{
			int mid = (l+r)>>1;
			if (up[mid] < a[cur]) r = mid;
			else l = mid + 1;
		}
		int b = up[l];
		up[l] = a[cur];
		if (dfs(dep, cur+1, uu, dd)) return 1;
		up[l] = b;
	}
		
	if (!dd || down[dd]<=a[cur])
	{
		down[dd+1] = a[cur];
		if (dfs(dep, cur+1, uu, dd+1)) return 1;
	}
	else {
		int l=1, r=dd;
		while (l < r)
		{
			int mid = (l+r)>>1;
			if (down[mid] > a[cur]) r = mid;
			else l = mid + 1;
		}
		int b = down[l];
		down[l] = a[cur];
		if (dfs(dep, cur+1, uu, dd)) return 1;
		down[l] = b;
	}
	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;
}