BZOJ2044: 三维导弹拦截

2044: 三维导弹拦截

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 175 Solved: 76
[Submit][Status]

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国的所有导弹？不管是为了个人荣誉还是国家容易，更多的是为了饭碗，你，都应该好好的把这个问题解决掉！

Input

第一行一个整数N给出B国导弹的数目。接下来N行每行三个非负整数Xi, Yi, Zi给出一个导弹的位置，你可以假定任意两个导弹不会出现在同一位置。

Output

第一行输出一个整数P，表示一枚拦截导弹之多能够摧毁的导弹数。第二行输出一个整数Q，表示至少需要的拦截导弹数目。

Sample Input

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

Sample Output

3
2

HINT

所有的坐标都是[0，10^6]的整数
对于30%的数据满足N < 31
对于50%的数据满足N < 101
对于100%的数据满足N < 1001

Source

第一届“NOIer”全国竞赛 By ghy

题解：

数组开小了你给我爆WA，呵呵。。。呵。。。

第一问刚开始想了想n^2没问题，如果打了 i 之后能打 j，那么就连边（i，j）

这张图显然是一个DAG，求最长链就可以

然后又想了想发现按一维排序之后n^2 DP也可以搞？

好象是这样的，因为题目要求每一维都严格单调，所以一维相同的顺序不影响，如果不严格上升的话还是最长链吧。。。

之所以按原来的顺序不能DP，是因为没有一个递推的顺序，所以我们按一维排序。（记忆化可以搞？）

第二问的话其实在上面的DAG上求一个最小路径覆盖就可以了。匈牙利算法OK。

代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 1005
 26 
 27 #define maxm 500+100
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 1000000007
 44 
 45 using namespace std;
 46 
 47 inline int read()
 48 
 49 {
 50 
 51     int x=0,f=1;char ch=getchar();
 52 
 53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 54 
 55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 56 
 57     return x*f;
 58 
 59 }
 60 struct rec{int x,y,z;}a[maxn];
 61 struct edge{int go,next;}e[maxn*maxn];
 62 int p[2*maxn],n,m,tot,head[2*maxn],f[2*maxn];
 63 bool v[2*maxn];
 64 inline void insert(int x,int y)
 65 {
 66     e[++tot].go=y;e[tot].next=head[x];head[x]=tot;
 67 }
 68 inline bool find(int x)
 69 {
 70     for(int i=head[x],y;i;i=e[i].next)
 71     {
 72         if(v[y=e[i].go])continue;
 73         v[y]=1;
 74         if(p[y]==0||find(p[y]))
 75         {
 76             p[y]=x;
 77             return 1;
 78         }
 79     }
 80     return 0;
 81 }
 82 inline bool cmp(rec a,rec b)
 83 {
 84     return a.x<b.x;
 85 }
 86 
 87 int main()
 88 
 89 {
 90 
 91     freopen("input.txt","r",stdin);
 92 
 93     freopen("output.txt","w",stdout);
 94 
 95     n=read();
 96     for1(i,n)a[i].x=read(),a[i].y=read(),a[i].z=read();
 97     sort(a+1,a+n+1,cmp);
 98     for1(i,n)f[i]=1;
 99     for2(i,2,n)
100      for1(j,i-1)
101       if(a[j].x<a[i].x&&a[j].y<a[i].y&&a[j].z<a[i].z)
102       {
103           insert(j,i+n);
104           f[i]=max(f[i],f[j]+1);
105       }
106     int ans=0;
107     for1(i,n)if(f[i]>ans)ans=f[i];
108     printf("%d
",ans);
109     ans=0;
110     for1(i,n)
111     {
112         memset(v,0,sizeof(v));
113         if(find(i))ans++;
114     }
115     printf("%d
",n-ans);
116 
117     return 0;
118 
119 }

View Code