题目1085: 拦截导弹-白红宇

题目1085: 拦截导弹

阅读量：4104 次

发布时间：2019-05-25

本文共 1345 字，大约阅读时间需要 4 分钟。

题目描述

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。

输入

每组输入有两行，第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。

输出

每组输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。

样例输入

4 9 6 7 8 7 4 5 6 7 13 42 3 5 6 5 4 3 5 0

样例输出

2 2 4

提示 [+]

*** 提示已隐藏，点击上方 [+] 可显示 ***

来源

【思路】

具体参考：

/**********************************   日期：2013-3-25*   作者：SJF0115*   题号: 题目1085: 拦截导弹*   来源：http://acmclub.com/problem.php?id=1085*   结果：AC*   来源：2007年北京大学计算机研究生机试真题*   总结：**********************************/#include
   
    #include
    
     int Height[26];int MaxLen[26];void LIS(int k){	memset(MaxLen,0,sizeof(MaxLen));	for(int i = 1;i <= k; i++){		MaxLen[i] = 1;		//遍历其前所有导弹高度		for(int j = 1;j < i;j++){			//如果当前导弹高度小于等于j号导弹			if(Height[i] <= Height[j]){				//把当前导弹放在j号导弹后，其最长不增子序列长度为j号导弹结尾的最长不增子序列长度 + 1				int preMax = MaxLen[j] + 1;				if(preMax > MaxLen[i]){					MaxLen[i] = preMax;				}			}		}	}} int main(){	int N,i;	//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);	while(scanf("%d",&N)!=EOF){		//输入导弹高度		for(i = 1;i <= N;i++){			scanf("%d",&Height[i]);		}		LIS(N);		int Max = -1;		//输出最长不增子序列的长度即能拦截的导弹数		for(i = 1;i <= N;i++){			if(Max < MaxLen[i]){				Max = MaxLen[i];			}		}		if(N != 0){			printf("%d\n",Max);		}	}	return 0;}

转载地址：http://sucsi.baihongyu.com/

你可能感兴趣的文章

Leetcode 1180. Count Substrings with Only One Distinct Letter [Python]