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。
分类标签 Tags
**动态规划**
/*
n^2 60.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 50001
using namespace std;
int n,tot,ans;
struct data{
int x,y,tot;
}s[MAXN*6];
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
bool cmp(const data & x,const data & y)
{
if(x.x!=y.x) return x.x<y.x;
return x.y<y.y;
}
int main()
{
int x,y,z;
n=read();
for(int i=1;i<=n;i++)
{
x=read();y=read();z=read();
s[++tot].x=x;s[tot].y=y;s[++tot].x=y;s[tot].y=x;
s[++tot].x=y;s[tot].y=z;s[++tot].x=x;s[tot].y=z;
s[++tot].x=z;s[tot].y=x;s[++tot].x=z;s[tot].y=y;
}
sort(s+1,s+tot+1,cmp);
for(int i=1;i<=tot;i++)
{
s[i].tot=1;
for(int j=i-1;j>=1;j--)
{
if(s[i].y>s[j].y&&s[i].x>s[j].x)
s[i].tot=max(s[i].tot,s[j].tot+1);
}
}
for(int i=1;i<=tot;i++)
ans=max(ans,s[i].tot);
printf("%d",ans);
return 0;
}
/*
nlogn.
左端点排序.
右端点从大到小排序.
防止左端点相等的点被更新.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 50001
using namespace std;
int n,tot,ans,l=1,c[MAXN*6];
struct data{
int x,y,tot;
}s[MAXN*6];
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
int erfen(int x){
int ll=0,r=l,mid;
while(ll<r){
mid=(r+ll)>>1;
if(x>c[mid]) ll=mid+1;
else r=mid;
}
return ll;
}
bool cmp(const data & x,const data & y)
{
if(x.x!=y.x) return x.x<y.x;
return x.y>y.y;
}
int main()
{
int x,y,z;
n=read();
for(int i=1;i<=n;i++)
{
x=read();y=read();z=read();
s[++tot].x=x;s[tot].y=y;s[++tot].x=y;s[tot].y=x;
s[++tot].x=y;s[tot].y=z;s[++tot].x=x;s[tot].y=z;
s[++tot].x=z;s[tot].y=x;s[++tot].x=z;s[tot].y=y;
}
sort(s+1,s+tot+1,cmp);
c[1]=s[1].y;
for(int i=2;i<=tot;i++)
{
s[i].tot=1;
if(s[i].y>c[l]) c[++l]=s[i].y;
else {
int p=erfen(s[i].y);c[p]=s[i].y;
}
}
printf("%d",l);
return 0;
}