描述 Description
一场战争正在 A 国与 B 国之间如火如荼的展开。
B 国凭借其强大的经济实力开发出了无数的远程攻击导弹，B 国的领导人希望，通过这些导弹直接毁灭 A 国的指挥部，从而取得战斗的胜利！当然，A 国人民不会允许这样的事情发生，所以这个世界上还存在拦截导弹。
现在，你是一名 A 国负责导弹拦截的高级助理。
B 国的导弹有效的形成了三维立体打击，我们可以将这些导弹的位置抽象三维中间的点（大小忽略），为了简单起见，我们只考虑一个瞬时的状态，即他们静止的状态。
拦截导弹设计非常精良，可以精准的引爆对方导弹而不需要自身损失，但是 A 国面临的一个技术难题是，这些导弹只懂得直线上升。精确的说，这里的直线上升指 xyz 三维坐标单调上升。
给所有的 B 国导弹按照 1 至 N 标号，一枚拦截导弹可以打击的对象可以用一个 xyz 严格单调上升的序列来表示，例如：
B 国导弹位置：(0, 0, 0) (1, 1, 0) (1, 1, 1), (2, 2, 2)
一个合法的打击序列为：{1, 3, 4}
一个不合法的打击序列为{1, 2, 4}
A 国领导人将一份导弹位置的清单交给你，并且向你提出了两个最简单不过的问题（假装它最简单吧）：
1．一枚拦截导弹最多可以摧毁多少 B 国的导弹？
2．最少使用多少拦截导弹才能摧毁 B 国的所有导弹？
不管是为了个人荣誉还是国家容易，更多的是为了饭碗，你，都应该好好的把这个问题解决掉！
输入格式 InputFormat
第一行一个整数 N 给出 B 国导弹的数目。
接下来 N 行每行三个非负整数 Xi, Yi, Zi 给出一个导弹的位置，你可以假定任意两个导弹不会出现在同一位置。
输出格式 OutputFormat
输出文件有且仅有两行。
第一行输出一个整数 P，表示一枚拦截导弹之多能够摧毁的导弹数。
第二行输出一个整数 Q，表示至少需要的拦截导弹数目。
样例输入 SampleInput
10
3 0 4
4 3 3
4 1 3
1 2 3
3 2 4
3 4 1
1 1 2
4 1 0
4 4 2
3 0 2
样例输出 SampleOutput
2
8
数据范围和注释 Hint
所有的坐标都是 [0，10^6] 的整数
对于 30% 的数据满足 N < 31
对于 50% 的数据满足 N < 101
对于 100% 的数据满足 N < 1001
代码 Code
第一问 DP 求严格递增，第二问拆点二分图匈牙利算法求最小路径覆盖。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
struct point
{
int z,y,x;
};
point a[1001];
int f[1001];
bool used[5001];
int adj[1001][1001];
int mat[5001];
int i,j,t,n,m,l,r,k,z,y,x,ans,match;
bool smaller(point a,point b)
{
if (a.x<b.x && a.y<b.y && a.z<b.z) return true;
return false;
}
void lis()
{
memset(f,0,sizeof(f));
for (i=1;i<=n;i++)
{
for (j=1;j<i;j++) if (smaller(a[j],a[i])) f[i]=max(f[i],f[j]);
f[i]++;
}
z=0;
for (i=1;i<=n;i++) z=max(z,f[i]);
printf("%dn",z);
}
bool comp(point a,point b)
{
if (a.x!=b.x) return a.x<b.x;
else if (a.y!=b.y) return a.y<b.y;
else if (a.z!=b.z) return a.z<b.z;
else return true;
}
void build()
{
int i,j,t;
memset(adj,0,sizeof(adj));
for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (smaller(a[i],a[j])) adj[j][++adj[j][0]]=i;
}
bool crosspath(int k)
{
int i,j,t;
for (i=1;i<=adj[k][0];i++)
{
j=adj[k][i];
if (!used[j])
{
used[j]=true;
if (mat[j]==0 || crosspath(mat[j]))
{
mat[j]=k;
return true;
}
}
}
return false;
}
void hungary()
{
int i,j,t;
match=0;
for (i=1;i<=n;i++)
{
if (crosspath(i)) match++;
memset(used,0,sizeof(used));
}
}
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a+1,a+n+1,comp);
lis();
build();
hungary();
printf("%d\n",n-match);
return 0;
}