Description

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。 敌国的导弹形成了立体打击，每个导弹可以抽象成一个三维空间中的点(x; y; z)。拦截系统发射的炮弹也很好地应对了这种情况，每一发炮弹也可以视为一个三维空间中的点。 但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达三维空间中任意的点，但是以后每一发炮弹到达点的坐标(x; y; z) 的三个坐标值都必须大于前一发炮弹的对应坐标值。 某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹飞来的坐标，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。注意: 所有导弹都是同时飞来的。

Input

第一行一个正整数n，表示敌国导弹数目。 接下来n 行，每行三个非负整数xi，yi，zi，表示一个敌国导弹的三维坐标。 数据保证所有的导弹坐标互不相同。

Output

第一行一个整数，表示一套系统最多拦截的导弹数。 第二行一个整数，表示拦截所有导弹最少配备的系统数。

Sample Input

4 0 0 0 1 1 0 1 1 1 2 2 2

Sample Output

3 2

Data Constraint

对于30% 的数据，n <=10 对于100% 的数据，n <= 1000，x; y; z <= 10^6

Solution

第一问是一个最长不下降子序列，n^2 dp，第二问是最小链覆盖，用匈牙利算法。

Code

#include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define I int #define ll long long #define F(i,a,b) for(I i=a;i<=b;i++) #define Fd(i,a,b) for(I i=a;i>=b;i--) #define mem(a,b) memset(a,b,sizeof a) #define N 1002 using namespace std; void R(I &x){ I w=1;x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} x*=w; } I n,f[N],m[N*2],bz[N*2],ans,cnt; I t[N*N],nx[N*N],ls[N<<1],tot; struct node{I x,y,z;}a[N]; I dfs(I x){ for(I k=ls[x];k;k=nx[k]){ if(bz[t[k]]) continue; bz[t[k]]=1; if(m[t[k]]==-1||dfs(m[t[k]])){ m[t[k]]=x; return 1; } } return 0; } I cmp(node x,node y){return x.x<y.x;} void add(I x,I y){ t[++tot]=y,nx[tot]=ls[x],ls[x]=tot; } I main(){ freopen("missile.in","r",stdin); freopen("missile.out","w",stdout); R(n); F(i,1,n) R(a[i].x),R(a[i].y),R(a[i].z); sort(a+1,a+1+n,cmp); a[0]=node{-1,-1,-1}; F(i,1,n){ F(j,0,i-1) if(a[i].x>a[j].x&&a[i].y>a[j].y&&a[i].z>a[j].z) f[i]=max(f[i],f[j]+1); ans=max(ans,f[i]); } printf("%d\n",ans); F(i,1,n){ F(j,1,i-1) if(i!=j&&a[i].x>a[j].x&&a[i].y>a[j].y&&a[i].z>a[j].z) add(j,n+i); } mem(m,255); F(i,1,n){ mem(bz,0); cnt+=dfs(i); } printf("%d\n",n-cnt); return 0; }