poj1065 Wooden Sticks(교차하는 요소가 없는 lis의 줄 수)

제목: 막대기 n개를 드리겠습니다. 막대기는 두 가지 속성이 있습니다. l와 w가 있습니다. 기계를 켜서 이 막대기를 가공합니다. l1<=l2와 w1<=w2를 만족시키면 막대기 1을 가공한 후에 막대기 2를 가공할 수 있습니다. 그렇지 않으면 기계를 다시 가동해야 합니다. 최소 몇 번을 가동해야 합니까?제목의 뜻은 다음과 같다. 몇 개의 편차를 제시하고 이런 집합의 크기를 구하면 이 집합에서 임의의 두 개의 편차를 비교할 수 없다.
분석: 만약에 막대기를 그 중의 한 속성에 따라 승차(속성값이 같으면 다른 속성값에 따라 승차)하면 다른 속성의 lis체인의 최소 개수를 구하고 각 lis체인 사이에 같은 아래 표시된 요소가 포함되지 않도록 요구한다.
한층 더 분석하면 결론을 얻을 수 있다. 가장 적은 최장 불강자 서열의 체인 수는 변환할 수 있고 가장 긴 하강자 서열의 길이를 구할 수 있다. 왜냐하면 하강자 서열의 원소는 반드시 같은 체인에 넣을 수 없고 서로 다른 체인에만 놓을 수 있기 때문이다. 그러면 가장 적은 체인 수는 가장 긴 하강자 서열의 길이이다.

#include
#include
#include
#include
using namespace std;
const int maxn=5000;
const int inf=0x3f3f3f3f;

pair<int,int>s[maxn+5];

int n;
int a[maxn+5];
int g[maxn+5];

int lis(){//         
    int ans=0;
    memset(g,inf,sizeof(g));
    for(int i=1;i<=n;i++){
        int k=lower_bound(g+1,g+1+n,a[i])-g;
        g[k]=a[i];
        ans=max(ans,k);
    }
    return ans;//      
}

int main(){
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>s[i].first>>s[i].second;
        }
        sort(s+1,s+1+n);// l  ，l   w  
        for(int i=1;i<=n;i++)a[i]=s[i].second;
        reverse(a+1,a+1+n);//            ，              ，     
        cout<