HDU 1667 Nested Dolls

3306 ワード

この問題は2点の方法で使用されます.
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
class Node
{
public:
int h,w;
};
bool cmp( Node a ,Node b )
{
if( a.w == b.w )
return a.h > b.h;
return a.w < b.w;
}
Node doll[20024];
int Doll( int n )
{
int sum=0;
int hash[20024]={0};
for( int i = 0; i< n ; i++ )
{
int l = 0 ,r = sum;
while( l < r )
{
int k = ( l + r )>>1;
if( hash[k]>=doll[i].h )
l = k + 1;
else r = k;
}
hash[l] = doll[i].h;
if( l == sum ) sum++;
}
return sum;
}
int main( )
{
int n,m;
while( scanf( "%d",&n )==1 )
{
for( int i = 0; i< n ; i++ )
{
scanf( "%d",&m );
for( int j = 0 ; j< m ; j++ )
scanf( "%d%d",&doll[j].w, &doll[j].h );
sort( doll , doll + m ,cmp );
printf( "%d
",Doll( m ) );
}
}
return 0;
}