2020.10.17 JZOJ 提高B组T2 导弹拦截

题目

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

题解

题意

就是那道大家都很熟悉的导弹拦截的升级版
每个导弹是三维中的一个点，导弹同时发射，拦截系统除第一发外，其余的都要满足比前一发的坐标值大，问最大拦截个数和还需多少系统

题解

第一问直接DP，按(x)排序，比较(y,z)，(f[i]=max(f[j]+1))
第二问想贪心，但不行
发现如果可以从(j)转移到(i)，就连一条(j)到(i)的边
然后把一个点拆成两个点，就形成了一个二分图
思考发现答案就是总点数-最大匹配，匈牙利算法
至于二分图最大匹配不熟的，这里有道板子题：UOJ #78 二分图最大匹配

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
	int x,y,z;
}a[1001];
int n,ans,num,f[1001],fa[2001],map[2002][2002];
bool b[2001];
int read()
{
	int res=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();	
	return res;
}
bool cmp(node x,node y) {return x.x<y.x;}
bool judge(int x)
{
	for (int i=1;i<=map[x][0];++i)
	{
		if (!b[map[x][i]])
		{
			b[map[x][i]]=true;
			if (!fa[map[x][i]]||judge(fa[map[x][i]]))
			{
				fa[map[x][i]]=x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	freopen("missile.in","r",stdin);
	freopen("missile.out","w",stdout);
	n=read();
	for (int i=1;i<=n;++i)
		a[i].x=read(),a[i].y=read(),a[i].z=read();
	sort(a+1,a+n+1,cmp);
	for (int i=1;i<=n;++i)
	{
		f[i]=1;
		for (int j=1;j<i;++j)
			if (a[i].y>a[j].y&&a[i].z>a[j].z)
			{
				f[i]=max(f[i],f[j]+1);
				map[j<<1][++map[j<<1][0]]=i<<1|1;
			}
	}
	for (int i=1;i<=n;++i)
		ans=max(ans,f[i]);
	printf("%d
",ans);
	for (int i=2;i<=n<<1;i+=2)
	{
		memset(b,false,sizeof(b));
		if (judge(i)) ++num;
	}
	printf("%d
",n-num);
	fclose(stdin);
	fclose(stdout);
	return 0;
}