Poj Solution 3214

http://poj.org/problem?id=3214

#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( "%dn", n - h );

    return 0;
}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *