建造高塔（codevs 1689）

题目描述 Description

n有n种石块，石块能无限供应。每种石块都是长方体，其中第i种石块的长、宽、高分别为li、wi、hi。石块可以旋转，使得其中两维成为长度和宽度，第三维成为高度。如果要把一个石块放在另一个石块上面，必须保证上面石块的长和宽都分别严格小于下面石块的长和宽。这意味着，即使两块长宽相同的石块也不能堆砌起来。

现在神犇想知道，最多能用上多少块石头呢？

 

输入描述 Input Description

第一行，N； 
以下N行，每行三个数，表示第i种石头的长宽高。

输出描述 Output Description

一个整数，表示最多能用上多少块石头。

样例输入 Sample Input

3

1 1 1

2 2 2

3 3 4

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

N≤50000，其余数字≤maxlongint。

/*
  二分的最长严格上升子序列，因为是严格的，所以按照a排序时，b要从大  
  到小排，曾经试过二维的，但怎么改都不对。
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define M 300010
using namespace std;
int f[M],cnt;
struct node
{
    int a,b;
};node e[M];
int n;
bool cmp(const node&x,const node&y)
{
    if(x.a<y.a)return 1;
    if(x.a==y.a&&x.b>y.b)return 1;
    return 0;
}
int erfen(int l,int r,int x)
{
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(f[mid]>=x)r=mid-1;
        else l=mid+1;
    }
    return l;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[++cnt].a=x;e[cnt].b=y;e[++cnt].a=y;e[cnt].b=x;
        e[++cnt].a=x;e[cnt].b=z;e[++cnt].a=z;e[cnt].b=x;
        e[++cnt].a=y;e[cnt].b=z;e[++cnt].a=z;e[cnt].b=y;
    }
    sort(e+1,e+cnt+1,cmp);
    f[1]=e[1].b;int len=1;
    for(int i=2;i<=cnt;i++)
      if(e[i].b>f[len])
        f[++len]=e[i].b;
      else
      {
          int pos=erfen(1,len,e[i].b);
          f[pos]=e[i].b;
      }
    printf("%d",len);
    return 0;
}