记录编号	97988	评测结果	AAAAAAAAAA
题目名称	导弹拦截	最终得分	100
用户昵称	GDFRWMY	是否通过	通过
代码语言	C++	运行时间	0.227 s
提交时间	2014-04-21 14:55:23	内存使用	35.98 MiB

#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
ifstream fin("bomba.in");
ofstream fout("bomba.out");
class xxx{
public:
	int x,y,z;
};
xxx k[50000];
int n,ans,flag[50000],f[50000],sum,vis[50000],fa[50000];
int map[3000][3000];
bool operator <(xxx a,xxx b){
return (a.x < b.x && a.y < b.y && a.z < b.z);
}
/*void dfs(int x){
	for(int i=x+1;i<=n;i++)
		if (flag[i]==0&&k[x]<k[i]){
			flag[i]=1;
			dfs(i);
			return;
		}
}
	*/		
bool dfs(int x){
	for (int i=n;i<=n+n;i++){
		if (map[x][i]&&vis[i]==0){
			vis[i]=1;
            if (fa[i]==0||dfs(fa[i])){
            fa[i]=x;
            return true;
            }
	    }
	}
return false;
}
 
	

bool cmp(xxx a,xxx b){
	if (a.x < b.x) return 1;
    if (a.x > b.x) return 0;
    if (a.y < b.y) return 1;
    if (a.y > b.y) return 0;
	return a.z < b.z;
}	

int main(){
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>k[i].x>>k[i].y>>k[i].z;
	sort(k+1,k+n+1,cmp);
	f[1]=1;
	for(int i=2;i<=n;i++){
		f[i]=1;
		for (int j=1;j<i;j++)
			if (f[i]<f[j]+1&&k[j]<k[i])
				f[i]=f[j]+1;
	}
	ans=0; 
	for(int i=1;i<=n;i++) if (ans<f[i]) ans=f[i];
    fout<<ans<<endl;
	ans=0;
	/*for(int i=1;i<=n;i++)
		if (flag[i]==0){
			ans++;
			flag[i]=1;
			dfs(i);
		}
	fout<<ans;*/
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if (k[i]<k[j])
				map[i][j+n]=map[i+n][j]=1;
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if (dfs(i)) sum++;
	}
	fout<<n-sum;
	
return 0;
}