某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若 i<j，则 Li<=Lj，Wi<=Wj）的序列。请问至少要分成几组?

第一行为一个整数 N（N<=1000），表示零件的个数。第二行有 N 对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过 10000。

仅一行，即最少分成的组数。

5

8 4 3 8 2 3 9 7 3 5

2

解题思路：动态规划求最大递减子序列（最少分组数=最大反链数_dilworth定理）

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

struct node{

    int l;

    int w;

};

node a[];

int cmp(node a,node b){

    return a.l<b.l||a.l==b.l&&a.w<b.w;

}

int main()

{

    int n;

    int sum[];

    scanf("%d",&n);

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

        scanf("%d %d",&a[i].l,&a[i].w);

        sum[i]=;

    }

    sort(a,a+n,cmp);

    int ans=;

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

        int maxx=;

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

            if(a[j].w>a[i].w){

                maxx=max(maxx,sum[j]);

            }

        }

        sum[i]=maxx+;

        ans=max(ans,sum[i]);

    }

    printf("%d",ans);

    return ;

}