zoj 1025Wooden Sticks(贪心)

递增子序列的最小组数。可以直接贪心，扫一遍

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

struct stick{

    int h,w;

}Sticks[];

bool cmp(stick a,stick  b)

{

    return (a.h<b.h)||(a.h==b.h&&(a.w<b.w));

}

int main(void)

{

    int n;

    int t;

    cin>>t;

    while(t--)

    {

        cin>>n;

        for(int i=;i<n;i++){

            cin>>Sticks[i].h>>Sticks[i].w;

        }

        sort(Sticks,Sticks+n,cmp);

        int cnt=;

        int bzw[]={};

        for(int i=;i<n;i++)

        {

            if(bzw[i]==)

            {

                cnt++;

                int temp=Sticks[i].w;

                for(int j=i+;j<n;j++)

                {

                    if(bzw[j]==&&temp<=Sticks[j].w)

                    {

                        bzw[j]=;

                        temp=Sticks[j].w;

                    }

                }

            }

        }

        cout<<cnt<<endl;

    }

    return ;

}