3214.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 76 行

Source

Problem Id:3214  User Id:fzk 
Memory:10544K  Time:1215MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v[20];
int a[2100000];
int t[2100000];
int n, m, h;
int vn[20];

void input( ) {
	int i, j;
	scanf( "%d", &m );
	for( i=0; i<m; i++ ) {
		
		v[i].resize( 1<<i );
		
		for( j=0; j<(1<<i); j++ )
			if( scanf( "%d", &v[i][j] ) != 1 )
				break;

		vn[i] = j;
	}
}
int offset = 0;

bool DFS( int i, int j ) {
	
	if( vn[i] <= j )
		return false;
	bool key = false;
	if( i < m-1 ) {
		key |= DFS( i+1, j*2 );
		key |= DFS( i+1, j*2+1 );
	}

	int k = n;
	a[k] = v[i][j];
	if( !key )
		offset ++;
	a[k] -= offset;
	n++;


	j = upper_bound( t, t+h, a[k] ) - t;
	if( j == h )
		t[h++] = a[k];
	else
		t[j] = a[k];
	return true;
}

int main()
{

	input( );
	n = 0;
	h = 0;
	DFS( 0, 0 );

	printf( "%d\n", n - h );

	return 0;
}