正文

codevs1409拦截导弹2

MashiroSky  MashiroSky  2022-08-06  580

关键词：

题意：给出n个三维的导弹，每次拦截只能打x，y，z严格上升的若干个导弹，求最多能一次拦截下多少个导弹，以及最少拦截几次将所有导弹全部拦截。

Solution
　　第一问直接排序后n²的dp即可。
　　第二问我们考虑二分图匹配，连边后转换模型成为最小路径覆盖。

代码：

// codevs1409
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
using namespace std;

const int maxn=1010;
struct edge {int to,next;}e[maxn*maxn];
struct point {int x,y,z;}p[maxn];
int head[maxn],f[maxn],cnt,n,vis[maxn],t[maxn];

void link(int u,int v) {
    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
bool cmp(point a,point b) {
    return a.x<b.x;
}
int find(int x) {
    for (int i=head[x];i;i=e[i].next) if (vis[e[i].to]!=cnt) {
            vis[e[i].to]=cnt;
            if (!t[e[i].to] || find(t[e[i].to])) {
                    t[e[i].to]=x;
                    return 1;
            }
        }
    return 0;
}
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
    sort(p+1,p+1+n,cmp);
    int ans=0;
    for (int i=1;i<=n;i++) {
        f[i]=1;
        for (int j=1;j<i;j++)
            if (p[i].x>p[j].x && p[i].y>p[j].y && p[i].z>p[j].z) f[i]=max(f[i],f[j]+1),link(i,j);
        ans=max(ans,f[i]);
    }
    printf("%d
",ans);
    ans=cnt=0;
    for (int i=1;i<=n;i++) {
        cnt++;ans+=(!find(i));
    }
    printf("%d",ans);
    return 0;
}

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最少拦截系统

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