hdu1257 最少拦截系统--DP
发布日期:2021-10-03 20:31:57
浏览次数:5
分类:技术文章
本文共 1071 字,大约阅读时间需要 3 分钟。
原题链接:
一:原题内容
Problem Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
二:分析理解
求最长递减序列的个数
三:AC代码
#include#include #include using namespace std;int dp[1005];//dp[i]代表第i个最长递减序列中当前状态的所含元素最小值 int main(){ int n; int x; while (~scanf("%d", &n)) { dp[1] = 0; int ans = 0;//最长递减序列的个数,也就是本题的答案 for (int i = 1; i <= n; i++) { scanf("%d", &x); int j; for (j = 1; j <= ans; j++) { if (x < dp[j]) { dp[j] = x; break; } } if (j > ans) dp[++ans] = x; } printf("%d\n", ans); } return 0;}
解法二:
dp[ i ]表示以i结尾的最长递增子序列的长度。
#includeint a[1000],d[1000]; int main() { int i,n,j,max; while(scanf("%d",&n)!=EOF) { for(i=0;i a[j]&&d[i]
转载地址:https://blog.csdn.net/LaoJiu_/article/details/50964138 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年03月01日 02时39分45秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
chmod 赋权所有_chmod 权限 命令详细用法
2019-04-21
html代码翻译_[译]您知道 HTML 的键盘标签吗?
2019-04-21
html抽奖代码_JavaScript高手之路:封装抽奖效果
2019-04-21
的流程图做完后如何保存_2019超火的半永久眉是哪款?做完后我们如何护理?...
2019-04-21
去除logo 高德地图api_深圳品牌logo升级如何保持原型的同时更具创新?
2019-04-21
二重积分转换成极坐标_二重积分转换极坐标r的范围如何确定?
2019-04-21
python中倒背如流_八字基础知识--倒背如流篇
2019-04-21
以太坊地址和公钥_以太坊地址是什么
2019-04-21
千层浪软件下载_千层浪app聚合
2019-04-21
npm 不重启 全局安装后_解决修复npm安装全局模块权限的问题
2019-04-21
vs格式化json 不生效_vs code 格式化 json 配置
2019-04-21
go 字符串反序列化成对象数组_Fastjson 1.2.24反序列化漏洞深度分析
2019-04-21
centos命令行安装mysql_CentOS7.6安装MYSQL8.0的步骤详解
2019-04-21
hibernate mysql 缓存_hibernate和mysql的缓存问题,没辙了!
2019-04-21
abp框架 mysql_ABP框架使用Mysql数据库
2019-04-21
mysql树形递归删除_使用递归删除树形结构的所有子节点(java和mysql实现)
2019-04-21
linux mysql 不能连接远程_linux mysql 远程连接
2019-04-21