题目1112:拦截导弹
时间限制:1 秒
内存限制:32 兆
特殊判题:否
提交:5218
解决:2603
- 题目描述:
-
某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,并观测到导弹依次飞来的高度,请计算这套系统最多能拦截多少导弹。拦截来袭导弹时,必须按来袭导弹袭击的时间顺序,不允许先拦截后面的导弹,再拦截前面的导弹。
- 输入:
-
每组输入有两行,第一行,输入雷达捕捉到的敌国导弹的数量k(k<=25),
第二行,输入k个正整数,表示k枚导弹的高度,按来袭导弹的袭击时间顺序给出,以空格分隔。
- 输出:
-
每组输出只有一行,包含一个整数,表示最多能拦截多少枚导弹。
- 样例输入:
-
8
300 207 155 300 299 170 158 65
- 样例输出:
-
6
#include <stdio.h>
int max(int a, int b) {return a>b?a:b;}
int list[];
int dp[];
int main() {
int n;
while(scanf("%d", &n) != EOF) {
for(int i = ; i <= n; i++) {
scanf("%d", &list[i]);
}
for(int i = ; i <= n; i++) {
int tmax = ;
for(int j = ; j < i; j++) {
if(list[j] >= list[i]) {
tmax = max(tmax, dp[j] + );
}
}
dp[i] = tmax;
}
int ans = ;
for(int i = ; i <= n; i++) {
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
}
return ;
}
九度OJ-1112-导弹拦截-最长不增子序列的更多相关文章
-
九度OJ 1112:拦截导弹 (DP、最长下降子序列)
时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:3124 解决:1525 题目描述: 某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能 ...
-
九度OJ 1337:寻找最长合法括号序列 (DP)
时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:839 解决:179 题目描述: 给你一个长度为N的,由'('和')'组成的括号序列,你能找出这个序列中最长的合法括号子序列么?合法括号序列的 ...
-
九度OJ 1535 重叠的最长子串
重叠的最长子串 http://ac.jobdu.com/problem.php?pid=1535 时间限制:1 秒 内存限制:128 兆 题目描述: 给定两个字符串,求它们前后重叠的最长子串的长度,比 ...
-
九度OJ 1342:寻找最长合法括号序列II (DP)
时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:898 解决:366 题目描述: 假如给你一个由'('和')'组成的一个随机的括号序列,当然,这个括号序列肯定不能保证是左右括号匹配的,所以给 ...
-
九度oj 题目1533:最长上升子序列
题目描述: 给定一个整型数组, 求这个数组的最长严格递增子序列的长度. 譬如序列1 2 2 4 3 的最长严格递增子序列为1,2,4或1,2,3.他们的长度为3. 输入: 输入可能包含多个测试案例. ...
-
九度oj 题目1530:最长不重复子串
题目描述: 最长不重复子串就是从一个字符串中找到一个连续子串,该子串中任何两个字符都不能相同,且该子串的长度是最大的. 输入: 输入包含多个测试用例,每组测试用例输入一行由小写英文字符a,b,c... ...
-
九度oj 题目1528:最长回文子串
题目描述: 回文串就是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串. 回文子串,顾名思义,即字符串中满足回文性质的子串. 给出一个只由小写英文字符a,b,c...x, ...
-
【九度OJ】题目1195:最长&最短文本 解题报告
[九度OJ]题目1195:最长&最短文本 解题报告 标签(空格分隔): 九度OJ http://ac.jobdu.com/problem.php?pid=1195 题目描述: 输入多行字符串, ...
-
九度OJ 1500 出操队形 -- 动态规划(最长上升子序列)
题目地址:http://ac.jobdu.com/problem.php?pid=1500 题目描述: 在读高中的时候,每天早上学校都要组织全校的师生进行跑步来锻炼身体,每当出操令吹响时,大家就开始往 ...
随机推荐
-
win7 安装JDK7和JDK8后,卸载JDK8后出错
这是本人学习Java过程中遇到的一些问题和解决方法,在此记录,方便本人查看,解决他人疑惑. 本人win7 x64旗舰版,同时安装了JDK7和JDK8,卸载了JDK8之后,cmd命令行输入:java - ...
-
更改Xampp-sql的默认密码-配置appche运行环境
用php编写的web应用程序,需运行在php的web容器中,其中apache server是一个针对php web容器,它是apache下的开源项目.通常要运行一个web程序,我们还需要安装数据库软件 ...
-
Android EditText输入最大值提示功能
public class LengthFilter implements InputFilter { public LengthFilter(int max) { mMax = max; } @Ove ...
-
python中%和format
两者都是格式化字符串用的,前者是比较老的版本,现在已经不推荐,后者更强大一些 % In [22]: print '%s' % 'hello world' hello world In [23]: pr ...
-
后台向前台输出 换行“\n”
MVC 中后台向前台输出 "\n"总是报错 因为后台向前台输出 "\n" 后,前台出现换行 eg: "这里是\n换行" var str=& ...
-
Java——交通灯
/* * 交通灯管理系统的 项目需求: * 模拟实现: 十字路口的交通灯系统逻辑, 具体需求如下: * 异步随机生成按照各个路线行驶的车辆. * 信号灯忽略黄灯. 只考虑红灯和绿灯. ...
-
基于vue的多引擎搜索及关键字提示
关键代码: <div class="header-search"> <form id="form" action="http://m ...
-
ASP.net 路径问题 详解
各位有没有碰到在日常工作中经常在路径设置的时候把 "~/ ../ .../ . / .http://www.cnblogs.com/"这些符号搞混搞乱了?偶尔还会因路径的问题郁闷了 ...
-
Pandas系列(十三)-其他常用功能
一.统计数据频率 1. values_counts pd.value_counts(df.column_name) df.column_name.value_counts() Series.value ...
-
《ABCD组团队》第二次作业
ABCD组:二手车价格预测系统 项目 内容 这个作业属于哪个课程 http://www.cnblogs.com/nwnu-daizh/ 这个作业的要求在哪里 https://www.cnblogs.c ...