HDUOJ----最少拦截系统

最少拦截系统

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 6   Accepted Submission(s) : 4

Problem Description

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

2

Source

浙江工业大学第四届大学生程序设计竞赛

 DP.....

比较简单吧!!

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 using namespace std;
 5 int main()
 6 {
 7   int n,a,i,j,len,flag;
 8   while(cin>>n)
 9   {
10      vector<int>arr(n);
11      len=0;
12      for(i=0;i<n;i++)
13      {
14          scanf("%d",&a);
15          flag=0;
16         for(j=1;j<=len;j++)
17         {
18             if(a>arr[j-1]&&a<=arr[j])
19             {
20                 arr[j]=a;
21                 flag=1;
22                 break;
23             }
24         }
25         if(flag==0)
26         { 
27             len++;
28             arr[len]=a;
29         }
30      }
31      cout<<len<<endl;
32   }
33   return 0;
34 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏域名资讯

域名资讯:近期交易的数字域名与拼音域名价格

数字域名流通性较强,而且建站上没有太大局限性,因此很是受投资人和终端喜爱。而拼音域名很符合中国互联网市场的需求,也是很多米农和企业喜欢的类型。近日...

27070
来自专栏ml

HDUOJ-----2068RPG的错排

RPG的错排 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

30850
来自专栏木东居士的专栏

程序员该如何管理后宫:和女生沟通的艺术(装饰模式)

22460
来自专栏架构说

leetcode打家劫舍问题

https://leetcode-cn.com/problems/house-robber/description/

21020
来自专栏生信宝典

跟Cell editor学做scientific presentation (25个判断标准,18个不能做,8个建议)

再多建议归根结底就是一句话:做事用心。想明白要表达什么,表达是不是清晰,表达是不是简洁,表达有无错误, 就可以了。下面的25个判断标准,18个不能做,8个建议是...

11410
来自专栏ml

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

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

31450
来自专栏牛客网

京东【Java实习】海外党远程二面

惯例先放一面面经链接:https://www.nowcoder.com/discuss/74319 直入正题: 1. JVM内存模型说一下? 2. GC回收的...

39370
来自专栏算法修养

HDU-1754 I Hate It(线段树)

阿里云-云翼计划礼上加礼#——买六个月送域名代金券! I Hate It Time Limit: 9000/3000 MS (Java/Others) M...

38740
来自专栏算法修养

HDU-1881 毕业bg (01背包变形)

毕业bg Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java...

44370
来自专栏腾讯Bugly的专栏

你为什么需要 Kotlin

导语 在当今的互联网时代,新技术犹如雨后春笋般层出不穷。精神哥之前也和开发同学一起讨论过程序员的成长离不开哪些软技能?当时很多人都有提到探究新技术对程序员的重要...

46240

扫码关注云+社区

领取腾讯云代金券