Logo CSP.ac

CSP.ac

1 s / 256 MB

#119. 【冬令营】Day1T2-偏序集

统计

【问题描述】

有n个三元组,第i个三元组是(x[i],y[i],z[i])。如果A=(u,v,w)和B=(x,y,z)满足u<=x,v<=y,w<=z,我们称A<=B,也可以说B>=A。这时,我们说A与B是可比较的。

例如(1,2,3)和(2,3,3)是可比较的。但(3,2,3)和(2,3,4)是不可比较的,我们没法比较它们的大小。

给出n个三元组,从其中选出若干三元组,使得选出的三元组两两可比较。求最多能选出多少个三元组。

【输入格式】

第一行一个整数n, 接下来n行,第i行三个正整数x[i]、y[i]、z[i]

【输出格式】

一行一个数,最多选出多少个三元组。

【样例输入】

4
5 5 2
3 3 2
1 6 2
1 1 1

【样例输出】

3

【样例解释】

选择第1、2、4个三元组

【数据规模和约定】

对于20%的数据, n<=8,z[i]=1 对于40%的数据, n<=1000,z[i]=1 对于60%的数据, n<=1000 对于100%的数据, n<=100000,1<=x[i],y[i]<=10^9,1<=z[i]<=2