1689 建造高塔
時間限制: 1 s
空間限制: 128000 KB
題目等級 : 鑽石 Diamond
題目描述 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。
/*
排序+LIS
O(n*n)做法可以的60分
剛開始打的n*n的最長上升子序列
*/
/*
排序時一點小技巧
把結構體按長從小到大排序
如果長相等則把寬大的排前面
這樣就可以轉化成求寬的最長上升子序列了
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 50010
using namespace std;
struct node
{
int l;
int s;
}e[maxn*6];
int n,tot,len,c[maxn*6];
int cmp(node x,node y)
{
if(x.l<y.l)return 1;
if(x.l==y.l&&x.s>=y.s)return 1;
return 0;
}
int main()
{
int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
e[++tot].l=x;e[tot].s=y;
e[++tot].l=x;e[tot].s=z;
e[++tot].l=y;e[tot].s=z;
e[++tot].l=y;e[tot].s=x;
e[++tot].l=z;e[tot].s=x;
e[++tot].l=z;e[tot].s=y;
}
sort(e+1,e+tot+1,cmp);
for(i=1;i<=tot;i++)
{
if(e[i].s>c[len])
c[++len]=e[i].s;
else
{
//int mx=lower_bound(c+1,c+len+1,e[i].s)-c;
int l=1,r=len,mx;
while(l<=r)
{
int mid=(l+r)/2;
if(e[i].s<=c[mid])
{
mx=mid;
r=mid-1;
}
else
l=mid+1;
}
c[mx]=e[i].s;
}
}
printf("%d
",len);
return 0;
}