专栏首页开心的学习之路算法训练 拦截导弹

算法训练 拦截导弹

问题描述

  某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。   输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

  一行,为导弹依次飞来的高度

输出格式

  两行,分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数

样例输入

389 207 155 300 299 170 158 65

样例输出

6 2 思路:        本题可以想作求输入序列的最长降序子序列,用数组dp记录以i结尾的序列长度,用Max更新最大值。用数组num记录以i为首的序列的编号,用Max2记录最大值。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

int dp[10000];
int a[10000];
int num[10000];

int main()
{
	freopen("input3.txt", "r", stdin);
	int i = 0, j, len, Max, Max2 = 1;
	do
	{
		scanf("%d", &a[i++]);
	}while(getchar() != '\n');
	len = i;
	Max = dp[0] = 1;
	Max2 = num[0] = 1;
	for(i = 1; i < len; i++)
	{
		dp[i] = 1;
		num[i] = 1;
		for(j = 0; j < i; j++)
		{
			if(a[i] < a[j] && dp[i] <= dp[j])
				dp[i] = dp[j] + 1;
			if(a[i] > a[j] && num[i] <= num[j])
				num[i] = num[j] + 1;
		}
		if(Max < dp[i])
			Max = dp[i];
		if(Max2 < num[i])
			Max2 = num[i];
	}
	printf("%d\n%d\n", Max, Max2);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 拦截导弹

    某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于等于前一发...

    书童小二
  • 拦截导弹

    某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高...

    AI那点小事
  • 又见拦截导弹

    大家对拦截导弹那个题目应该比较熟悉了,我再叙述一下题意:某国为了防御敌国的导弹袭击,新研制出来一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:它的第一发炮弹能...

    书童小二
  • nyoj------79拦截导弹

    拦截导弹 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统。但是这种导弹拦截系统...

    Gxjun
  • hdu----(1257)最少拦截系统(dp/LIS)

    最少拦截系统 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Ja...

    Gxjun
  • 动态规划 导弹拦截

    题意:一种导弹拦截系统的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有...

    Kindear
  • 【codevs1044】导弹拦截问题与Dilworth定理

    某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高...

    饶文津
  • 美国军方机密项目浮出水面:研发AI系统预测导弹发射国

    据路透社报道,美国军方正加大经费研究一种AI系统,它能预测朝鲜等国是否要发射核导弹,并可以追踪和瞄准移动发射器。

    量子位
  • 千人千面营销系统在携程金融支付的实践

    携程金融核心产品为:拿去花、借去花、信用卡、理财。其中拿去花提供携程产品分期支付服务,借去花提供现金借款服务,信用卡提供携程联名卡、理财则给用户提供有竞争力的理...

    携程技术
  • 完整的Java学习路线

    框架师
  • HDUOJ----最少拦截系统

    最少拦截系统 Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java...

    Gxjun
  • 关于硬实时

    这个限定时间超时后,所需的工作如果没有完成,那根据这个后果的严重程度,又可以分为硬实时和软实时。

    Taishan3721
  • When Does Machine Learning FAIL? Generalized Transferability for Evasion and Poisoning Attacks论文笔记

    该论文主要是介绍了一个FAIL模型, 即一个通用框架用来分析针对机器学习系统的真实攻击, 同时也提出了一种有目标的投毒攻击, 称作StingRay, 使得该攻击...

    Mezereon
  • 高科技也斗不过动物凶猛?荷兰对付无人机出高招了…

    老鹰抓到一台无人机并送回地面,然后得到了奖励:一块肉肉。老鹰的翅膀拍打着风、优雅地划过天空,然后张开利爪、向猎物俯冲。不过,这次的猎物并不是小鸟、不是小鱼,而是...

    机器人网
  • 【Bengio高徒演讲】深度学习三板斧:网络架构、学习算法和时空层级(48PPT)

    【新智元导读】Kyunghyun Cho是纽约大学计算机科学与数据科学助理教授。他是蒙特利尔大学博士后,导师是 Yoshua Bengio。他于2014年初在阿...

    新智元
  • 1044 拦截导弹 1999年NOIP全国联赛提高组 个人博客:attack.cf

    1044 拦截导弹 1999年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 ...

    attack
  • 2020攻防演练弹药库

    各位小伙伴们, 安全界一年一度的激动人心的攻防演练盛况即将来临:) 这里给大家准备些弹药, 主要是近些年的可以进后台/getshell的漏洞, 漏洞太多难免疏...

    洛米唯熊
  • 【典型案例】利用决策树实现乳腺癌预测助你成为半个医学专家

    乳腺癌是美国妇女最常见的癌症,也是癌症死亡的第二常见原因。利用机器学习算法从已有的临床乳腺癌数据中,可以学习导致乳腺癌的特征,并通过大量历史数据的学习使得机器成...

    腾讯智能钛AI开发者
  • 各位火绒弹窗拦截使用达人,这些隐藏小技巧你知道吗?

    本期互动话题:你遇到过最讨厌的弹窗广告是什么呢?在评论区告诉我们,我们会抽一位小伙伴送出火绒定制礼品一份哦。周一开奖哦~

    用户6477171

扫码关注云+社区

领取腾讯云代金券