零件分组_DP

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct node{
    int l;
    int w;
};
node a[1005];

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[1005];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d",&a[i].l,&a[i].w);
        sum[i]=0;
    }
    sort(a,a+n,cmp);
    int ans=0;
    for(int i=0;i<n;i++){
        int maxx=0;

        for(int j=0;j<i;j++){
            if(a[j].w>a[i].w){
                maxx=max(maxx,sum[j]);
            }
        }
        sum[i]=maxx+1;
        ans=max(ans,sum[i]);
    }
    printf("%d",ans);
    return 0;
}