1828:Monkeys' Pride

keyword

動的計画法　C++

概要

(x,y)のペアが与えられる。(x,y)>(x',y') を x>x' and y>y'で定義する。このとき、極大な元の個数を求める問題。ペアの個数は50000以下。
(x,y)を大きい順にソートする。yの最大値を覚えながら順になめていくと、yの最大値が更新されるときカウンタを増やせば良い。

int main(){
    int i, n, x, y, ans, ma;
    
    while(scanf("%d",&n)){
        if(!n) break;
        vector< pair<int, int> > ps(n);
        REP(i,n){
            scanf("%d%d",&x,&y);
            ps[i] = MP(x,y);
        }
        sort(ALL(ps), greater< pair<int,int> >());
        ans = 1;
        ma = ps[0].second;
        for(i=1;i<n;i++)if(ma < ps[i].second){
            ma = ps[i].second;
            ans++;
        }
        printf("%d\n",ans);
    }

    return 0;
}