2176970_tle.cc

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

# include <cstdio>
# include <vector>

using namespace std;

int i, n, H, A, x;
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 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
		{
			int 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;
}