POJ 1065 Wooden Sticks

经典的一道题

零件分组

每个零件有两维，将零件分组，要求每组内零件严格不下降，求最小组数

将一维排序，另一维求最长上升子序列即可

下面代码写的是暴力，也能过

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
struct lj
{
    int w,l;
}a[5010];
int n,ans=0,cnt=0,vis[6010];
int cmp(lj x,lj y)
{
    if (x.w==y.w) return x.l<y.l;
    return x.w<y.w;
}
int T;
int main()
{
  scanf("%d",&T);
  while(T--)
    {
      ans=cnt=0;
      memset(vis,0,sizeof(vis));
      scanf("%d",&n);
      for (int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].w);
      sort(a+1,a+n+1,cmp);
      while (cnt<n)
    {
      int tmp=-1;
      for (int i=1;i<=n;i++)
        {
          if (vis[i]==1) continue;
          else if (a[i].l>=tmp) {tmp=a[i].l;vis[i]=1;cnt++;}
        }
      ans++;
    }
      printf("%d
",ans);
    }
    return 0;
}