当前位置: 首页 > news >正文

网站型和商城型有什么区别搜索引擎名词解释

网站型和商城型有什么区别,搜索引擎名词解释,怎么免费建设个人网站,一个新手怎么去运营淘宝店铺概览检索 动态规划DP 最长上升子序列模型 拦截导弹 原题链接 AcWiing 1010. 拦截导弹 题目描述 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每…

概览检索
动态规划DP 最长上升子序列模型

拦截导弹

原题链接

AcWiing 1010. 拦截导弹

题目描述

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

某天,雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,导弹数不超过1000),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式
共一行,输入导弹依次飞来的高度。

输出格式
第一行包含一个整数,表示最多能拦截的导弹数。
第二行包含一个整数,表示要拦截所有导弹最少要配备的系统数。

数据范围
雷达给出的高度数据是不大于 30000
的正整数,导弹数不超过 1000。

输入样例:

389 207 155 300 299 170 158 65

输出样例:

6
2

题目分析

问题1

一套系统最多能拦截的导弹数?
每一发炮弹的高度不能高于前一发炮弹的高度则要求炮弹的高度单调递减,即为最长下降子序列的长度,由此转化为最长上升子序列模型LIS(点击链接跳转)。

最长上升子序列算法模板示例如下:

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n;
int a[N],f[N];  //a存储原始数据,f存储状态
/*要求:给定一个长度为 N的数列,求数值严格单调递增的子序列的长度最长是多少*/
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);//遍历以a[i]结尾的序列for(int i=1;i<=n;i++){f[i]=1;  //该序列中只有a[i],以a[i]结尾,长度为1//遍历在以a[i]结尾的序列下,倒数第二个数(即前一个数)为a[j]的序列for(int j=1;j<i;j++)if(a[j]<a[i])  //如果满足递增(前一个个数a[j]大于当前数a[i])f[i]=max(f[i],f[j]+1);  //则进行更新,取最大值}int res=0;//遍历以a[0]~a[n]结尾的最大上升子序列,其中的最大值即为所求值for(int i=1;i<=n;i++) res=max(res,f[i]);printf("%d",res);return 0;
}

问题2

拦截所有导弹最少要配备的系统数?
解决办法:贪心

思考过程:
第一个导弹:需要一个新系统拦截
第二个导弹:
两种选择:
1.可以用已有的系统拦截,接在现有的子序列之后;
2.建造一个新系统来拦截;
无论哪种选择,这个导弹就会成为某个现有子序列的结尾

当我们选择到第k个导弹时,前面已经建造了m个系统,即有m个下降序列,此时,我们面临着选择哪个系统(即接在哪个序列的后面)。
易知,序列结尾的数越大,在他后面能接上的数肯定就越多。因此,我们选择标准就是选择序列后,使剩余序列结尾的数尽可能的大
因此,我们就要选择当前m个序列中,满足序列结尾数大于等于当前第k个导弹高度的所有序列中,序列结尾数最小的那个序列(这样,选择较小的,剩下的序列结尾数就相对较大)。
如果当前不存在大于等于当前数的序列结尾数(即当前数不能放在任何序列的后面),则新建造一个新系统。

总结:
从前往后扫描每一个数,对于每个数:
情况1:如果当前所有子序列的结尾都小于当前数,则创建新的子序列;
情况2:否则,将当前数放到结尾大于等于它且最小子序列后面;

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n;
int a[N];
int f[N],g[N];
int main(){while(cin>>a[n]) n++;//问题1:最长下降子序列//f存储最长子序列的长度int res=0;for(int i=0;i<n;i++){f[i]=1;for(int j=0;j<i;j++){if(a[j]>=a[i])  //与上升"<="的区别f[i]=max(f[i],f[j]+1);}res=max(res,f[i]);}cout<<res<<endl;//问题2:最少系统数 贪心//g存储序列的结尾数int cnt=0;  //cnt存储总系统数//依次遍历每一个数for(int i=0;i<n;i++){int k=0;//遍历当前所有的子序列,找到满足序列结尾g[i]大于等于当前数a[i]的序列while(k<cnt&&g[k]<a[i]) k++;//情况1:找到满足要求的序列,放到序列结尾,更新当前序列结尾数//情况2:未找到满足要求的序列,此时k>=cnt,新建拦截系统,更新序列结尾数,更新总系统数cntg[k]=a[i];  //更新序列结尾数  if(k>=cnt) cnt++;  //若为情况2,系统总数+1}cout<<cnt<<endl;return 0;
}
http://www.zhongyajixie.com/news/13417.html

相关文章:

  • 专业团队建设实施方案北京seo学校
  • 360网站建设商家百度竞价推广怎么做
  • wordpress4.8速度慢郑州seo优化公司
  • 查询企业的app哪个好seo排名关键词
  • 腾讯客服网站在线客服怎么推广app让人去下载
  • 网页网站关系网站源码下载
  • 设备租赁业务网站如何做培训机构退费纠纷一般怎么解决
  • 宿州网站制作建设推广软文范例100字
  • 对于新闻网站运营问题今天刚刚的最新新闻
  • 石家庄网页设计招聘公司seo是什么级别
  • 返利的网站怎么做2022年适合小学生的新闻
  • 保定哪里做网站app推广拉新平台
  • 网站的风格网络热词2023
  • 静态购物网站模板怎么在网上做广告
  • 广州一网通办注册公司流程宣城网站seo
  • b2b独立站建站博客seo怎么做
  • 站长工具是什么网站结构优化
  • 朗格手表网站接广告推广
  • 做源码网站赚钱吗广州网站优化外包
  • 网站广告形式百度搜索引擎官网
  • 怀化网站建设怎么收费微信搜一搜seo优化
  • 单页面网站多少钱有道搜索
  • 长安网站建设费用优化大师使用方法
  • 商城网站页面设计百度贴吧官网网页
  • 手机端网站设计尺寸国外免费网站服务器
  • 用ip地址做网站镇江百度推广
  • 网站建设费怎样摊销宁波如何做seo排名优化
  • 我国外贸企业网站建设什么平台打广告比较好免费的
  • wp做音乐网站必备百度广告大全
  • 网站的发布与推广怎么写西安网是科技发展有限公司