Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
57 lines (39 sloc) 829 Bytes
/**
Jorge Alejandro Jimenez Luna
Algorithm: Catcher
*/
#include <bits/stdc++.h>
#define oo 1005
using namespace std;
int N;
struct two {
int up, down;
}A[oo];
bool dna (const two &s1, const two &s2) {
return s1.up < s2.up;
}
int Dp[oo];
int main ()
{
freopen ("Catcher.in", "r", stdin);
freopen ("Catcher.out", "w", stdout);
int Z, ZQ;
cin >> N;
for(int i = 0; i < N; i++){
cin >> Z >> ZQ;
A[i].up = Z;
A[i].down = ZQ;
}
sort(A, A + N, dna);
Dp[N] = 1;
int cost = 1;
int sol = 0;
for(int i = 0; i < N; i++){
Dp[i] = cost;
for(int j = 0; j < i; j++)
if(A[i].up > A[j].down)
Dp[i] = max(Dp[i], Dp[j] + cost);
sol = max(sol , Dp[i]);
}
cout << sol << endl;
}