百度网盟 网站定向投放,上海市网站设计,网站建设在哪里进行,外留网站建设概览检索 动态规划DP 最长上升子序列模型 拦截导弹
原题链接
AcWiing 1010. 拦截导弹
题目描述
某国为了防御敌国的导弹袭击#xff0c;发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷#xff1a;虽然它的第一发炮弹能够到达任意的高度#xff0c;但是以后每… 概览检索 动态规划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 N1010;
int n;
int a[N],f[N]; //a存储原始数据f存储状态
/*要求给定一个长度为 N的数列求数值严格单调递增的子序列的长度最长是多少*/
int main(){scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]);//遍历以a[i]结尾的序列for(int i1;in;i){f[i]1; //该序列中只有a[i]以a[i]结尾,长度为1//遍历在以a[i]结尾的序列下倒数第二个数即前一个数为a[j]的序列for(int j1;ji;j)if(a[j]a[i]) //如果满足递增前一个个数a[j]大于当前数a[i]f[i]max(f[i],f[j]1); //则进行更新取最大值}int res0;//遍历以a[0]~a[n]结尾的最大上升子序列其中的最大值即为所求值for(int i1;in;i) resmax(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 N1010;
int n;
int a[N];
int f[N],g[N];
int main(){while(cina[n]) n;//问题1最长下降子序列//f存储最长子序列的长度int res0;for(int i0;in;i){f[i]1;for(int j0;ji;j){if(a[j]a[i]) //与上升的区别f[i]max(f[i],f[j]1);}resmax(res,f[i]);}coutresendl;//问题2最少系统数 贪心//g存储序列的结尾数int cnt0; //cnt存储总系统数//依次遍历每一个数for(int i0;in;i){int k0;//遍历当前所有的子序列找到满足序列结尾g[i]大于等于当前数a[i]的序列while(kcntg[k]a[i]) k;//情况1找到满足要求的序列放到序列结尾更新当前序列结尾数//情况2未找到满足要求的序列此时kcnt新建拦截系统更新序列结尾数更新总系统数cntg[k]a[i]; //更新序列结尾数 if(kcnt) cnt; //若为情况2系统总数1}coutcntendl;return 0;
}
