http://wikioi.com/problem/1214/
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<bitset> #include<iomanip> using namespace std; #define maxn 1005 int dp[ maxn ] ; struct node { int left , right , value ; }edge[ maxn ] ; int cmp( const node a , const node b ) { return a.right < b.right ; } int main() { int n ; scanf( "%d" , &n ) ; { memset( edge , 0 , sizeof( edge ) ) ; for( int i = 1 ; i <= n ; ++i ) { scanf( "%d %d" , &edge[ i ].left , &edge[ i ].right ) ; if( edge[ i ].left > edge[ i ].right ) { int temp = edge[ i ].left ; edge[ i ].left = edge[ i ].right ; edge[ i ].right = temp ; } } sort( edge + 1 , edge + n + 1 , cmp ) ; edge[ 1 ].value = 1 ; for( int i = 2 ; i <= n ; ++i ) { for( int j = 1 ; j <= i - 1 ; ++j ) { if( edge[ i ].left >= edge[ j ].right ) { edge[ i ].value = max( edge[ i ].value , edge[ j ].value + 1 ) ; } } } int Max = 0 ; for( int i = 1 ; i <= n ; ++i ) { if( Max < edge[ i ].value ) Max = edge[ i ].value; } printf( "%d\n" , Max ) ; } return 0 ; }