首页 > 代码库 > BZOJ2044: 三维导弹拦截
BZOJ2044: 三维导弹拦截
2044: 三维导弹拦截
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 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
0 0 0
1 1 0
1 1 1
2 2 2
Sample Output
3
2
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\n",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",n-ans);116 117 return 0;118 119 }
BZOJ2044: 三维导弹拦截
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。