正文

codevs1409拦截导弹2

№〓→龙光←  №〓→龙光←  2022-08-06  665

关键词：

【问题描述】
一场战争正在 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 国的所有导弹?
不管是为了个人荣誉还是国家容易,更多的是为了饭碗,你,都应该好好的把这个问题解决掉!
【输入文件】
第一行一个整数 N 给出 B 国导弹的数目。
接下来 N 行每行三个非负整数 Xi, Yi, Zi 给出一个导弹的位置,你可以假定任意两个导弹不会出现在同一位置。
【输出文件】
输出文件有且仅有两行。
第一行输出一个整数 P,表示一枚拦截导弹之多能够摧毁的导弹数。
第二行输出一个整数 Q,表示至少需要的拦截导弹数目。
【输入输出样例】
输入
4
0 0 0
1 1 0
1 1 1
2 2 2
输出
3
2
【数据范围】
所有的坐标都是[0,10 6 ]的整数
对于 30%的数据满足 N < 31
对于 50%的数据满足 N < 101
对于 100%的数据满足 N < 1001

我们按照先后顺序连出一张DAG，第一问求的就是最长链，DP，搜都没有什么问题。第二问问要多少枚导弹，这不就是问这张DAG需要多少条路才能被完全覆盖，问题转换为可以走重复路径最小路径覆盖问题，网络流或匈牙利算法解决（若果你不会最小路径覆盖：http://www.cnblogs.com/Dragon-Light/p/5604865.html）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<vector>
 7 #include<cmath>
 8 #include<ctime>
 9 #include<cstring>
10 #define llg int
11 #define maxn 3010
12 #define md 1001000
13 using namespace std;
14 int dl[md+10],n,m,a[maxn][maxn],bj[maxn],ans=0,x,used[maxn],girl[maxn],y,i,j,k,f[maxn][maxn],val[maxn],deep[maxn],head,tail;
15 vector<llg>g[maxn];
16 struct node
17 {
18     llg a1,a2,a3;
19 }c[maxn];
20     
21 bool find(llg x)
22 {
23     for (llg i=1;i<=n*2;i++)
24     {
25         if (a[x][i] && !used[i])
26         {
27             used[i]=1;
28             if (!girl[i] || find(girl[i]))
29             {
30                 girl[i]=x;
31                 return true;
32             }
33         }
34     }
35     return false;
36 }
37 
38 llg BFS(llg x)
39 {
40     for (llg i=1;i<=n;i++) bj[i]=0;
41     dl[1]=x,head=0,tail=1; llg maxl=1,w; deep[x]=1;
42     do
43     {
44         head=(head % md)+1;
45         x=dl[head]; bj[x]=0;
46         maxl=max(maxl,deep[x]);
47         w=g[x].size();
48         for (llg i=0;i<w;i++)
49             if (deep[g[x][i]]<deep[x]+1)
50             {
51                 deep[g[x][i]]=deep[x]+1;
52                 if (!bj[g[x][i]])
53                 {
54                     deep[g[x][i]]=deep[x]+1;
55                     tail=(tail % md)+1;
56                     dl[tail]=g[x][i];
57                 }
58             }
59     }while (head!=tail);
60     return maxl;
61 }
62 
63 int main()
64 {
65     //yyj("bomb");
66     cin>>n;
67     for (i=1;i<=n;i++) scanf("%d%d%d",&c[i].a1,&c[i].a2,&c[i].a3);
68     for (i=1;i<=n;i++)
69         for (j=1;j<=n;j++)
70             if (c[i].a1<c[j].a1 && c[i].a2<c[j].a2 && c[i].a3<c[j].a3)
71             {
72                 f[i][j]=1;
73                 g[i].push_back(j);
74                 val[j]++;
75             }
76     for (i=1;i<=n;i++)
77         if (val[i]==0) ans=max(BFS(i),ans);
78     cout<<ans<<endl;
79 /*    for (k=1;k<=n;k++)
80         for (i=1;i<=n;i++)
81             for (j=1;j<=n;j++)
82                 f[i][j]=f[i][j] || (f[i][k] && f[k][j]);*/
83     for (i=1;i<=n;i++)
84         for (j=1;j<=n;j++)
85             if (i!=j && f[i][j]) a[i][n+j]=1;
86     ans=0;
87     for (i=1;i<=n*2;i++)
88     {
89         memset(used,0,sizeof(used));
90         if (find(i)) ans++;
91     }
92    cout<<n-ans;
93     return 0;
94 }

codevs1409拦截导弹2

...,A国人民不会允许这样的事情发生,所以这个世界上还存在拦截导弹。现在,你是一名A国负责导弹拦截的高级助理。B国的导弹有效的形成了三维立体打击,我们可以将这些导弹的位置抽象三维中间的点(大小忽略),为了简单起见,我们... 查看详情

codevs1044拦截导弹

1044拦截导弹 1999年NOIP全国联赛提高组时间限制:1s 空间限制:128000KB 题目等级:黄金Gold 题目描述 Description 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺... 查看详情

codevs1128导弹拦截

...escription经过11年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷... 查看详情

codevs1128导弹拦截

codevs1044拦截导弹1999年noip全国联赛提高组

1044拦截导弹 1999年NOIP全国联赛提高组时间限制:1s 空间限制:128000KB 题目等级:黄金Gold题解题目描述 Description 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截... 查看详情

codevs1044拦截导弹1999年noip全国联赛提高组

... 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来... 查看详情

洛谷p1158导弹拦截排序

---恢复内容开始---洛谷P1158导弹拦截排序算是有技巧的枚举吧题意用两套系统来拦截导弹，一个系统的费用等于这个系统拦截的导弹中离他最远的那颗导弹和系统的距离的平方排序将每颗导弹按距离系统1的距离排序，然后枚举n--... 查看详情

rqnojpid217/[noip1999]拦截导弹n^2/lis(代码片段)

题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来... 查看详情

拦截导弹问题(noip1999)(代码片段)

1322：【例6.4】拦截导弹问题(Noip1999)时间限制:1000ms 内存限制:65536KB提交数:3843 通过数:1373 【题目描述】某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一... 查看详情

导弹拦截

链接分析：经典DP题，最长不下降子序列的变种，同时需要记录路径，用pre[]数组记录当前结点的前一个结点的方法很妙1#include"iostream"2#include"cstdio"3#include"cstring"4#include"string"5#include"vector"6usingnamespacestd;7constintmaxn=110;8intdp[maxn];9intp 查看详情

导弹拦截(代码片段)

贪心4--拦截导弹

贪心4--拦截导弹一、心得二、题目和分析某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高... 查看详情

导弹拦截

47最少拦截系统(代码片段)

47 最少拦截系统作者: xxx时间限制: 1S章节: 一维数组问题描述:某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每... 查看详情

拦截导弹问题

拦截导弹动态规划问题某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到... 查看详情

hdu1257最少拦截系统

...感觉这题有些扯淡，难道要在敌军导弹发射后发现自己的拦截系统够不到的时候再去搞一套导弹拦截系统？提前准备多套导弹系统的花销是少不了的。只能是在使用的时候，在保证所有导弹被成功拦截的前提下，出动最少的数量... 查看详情