2176967_ce.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 65 行

# include <cstdio>
# include <vector>

using namespace std;

int i, n, H, A, x, max;
vector <int> h;
vector <int> a;
vector <int> dp;
char c;

void run(int m)
{
	if(2*m+1<H) run(2*m+1);
	if(2*(m+1)<H) {x++; run(2*(m+1));}
	a[A++]=h[m]-x;
}
int s(int m,int p,int q)
{
	int t;
	while(p<=q)
	{
		t=(p+q)/2;
		if(a[t]<=m) p=t+1;
		else
		{
			if(t-1<0||a[t-1]<=m) return t;
			else q=t-1;
		}
	}
	return -1;
}
int main()
{
	int tmp;

	H = 0;
	scanf("%d",&n);
	h.resize(1<<n);
	dp.resize(1<<n);
	while(scanf("%d",&tmp)==1)
	{	
		a.push_back(tmp);
		H++;
	}
	run(0);
	int ans = -1;
	for(i = 0; i < A; i++)
	{
		if(!i)
			dp[i] = 1;
		else
		{
			max = 0;
			for(int j = i - 1; j >= 0; j--)
				if(a[j]<=a[i]&&dp[j]>max)
					max = dp[j];
			dp[i] = max+1;
		}
		if(dp[i]>ans)
			ans = dp[i];
	}
	printf("%d\n",H-ans);
	return 1;
}