记录编号	98201	评测结果	AAAAAAAAAA
题目名称	导弹拦截	最终得分	100
用户昵称	隨風巽	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2014-04-21 21:06:11	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAXN=1000+10;
struct point{int x,y,z;}mis[MAXN];
int N,f[MAXN];
int max(int a,int b){return a>b?a:b;}
vector<int>g[MAXN];
bool cmp(point a,point b)
{
	if(a.x<b.x)return true;
	if(a.x>b.x)return false;
	if(a.y<b.y)return true;
	if(a.y>b.y)return false;
	return a.z<b.z;
}
struct KM
{
	int n,m;     // 左右顶点个数
	int left[MAXN];
	bool T[MAXN];// T[i]为右边第i个点是否已标记
	void INITIALIZE(int n,int m)
	{             
		this->n=n;this->m=m;
	}             
	bool MATCH(int u)
	{   	
		int i,v,un=g[u].size();
		for(i=0;i<un;i++)
		{	
			v=g[u][i];
			if(!T[v])
			{
				T[v]=true;
				if(left[v]==-1||MATCH(left[v]))
				{
					left[v]=u;
					return true;
				}
			}
		}
		return false;
	}
	int SOLVE(void)
	{
		memset(left,-1,sizeof(left));
		int ans=0,u;
		for(u=1;u<=n;u++)
		{
			memset(T,0,sizeof(T));
			if(MATCH(u))ans++;
		}
		return ans;
	}
};
KM BPM;
int main()
{
	freopen("bomba.in","r",stdin);
	freopen("bomba.out","w",stdout);
	scanf("%d",&N);
	int i,j,ans=0;
	for(i=1;i<=N;i++)
		scanf("%d%d%d",&mis[i].x,&mis[i].y,&mis[i].z);
	sort(mis+1,mis+1+N,cmp);
	//第一问
	for(i=1;i<=N;i++)f[i]=1;
	for(i=2;i<=N;i++)
	{
		for(j=i-1;j>=1;j--)
		{
			if(mis[i].x>mis[j].x&&mis[i].y>mis[j].y&&mis[i].z>mis[j].z)
				f[i]=max(f[j]+1,f[i]);
		}
	}
	for(i=1;i<=N;i++)
		ans=max(ans,f[i]);
	cout<<ans<<endl;
	//第二问
	for(i=1;i<=N;i++)
		for(j=i+1;j<=N;j++)
			if(mis[i].x<mis[j].x&&mis[i].y<mis[j].y&&mis[i].z<mis[j].z)
				g[i].push_back(j);
	BPM.INITIALIZE(N,N);
	cout<<N-BPM.SOLVE()<<endl;
	return 0;
}