代码：
java：
import java.util.Scanner;/********************************* * 题号: 题目1085: 拦截导弹 **********************************/public class intercept { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int height[] = new int[N];//存放导弹高度 int maxLen[] = new int[N];//存放每个导弹对应键值的拦截数量 int Max = -1;//最终结果，最大拦截数量 for (int i = 0; i < height.length; i++) {//输入所有导弹高度 height[i] = sc.nextInt(); } f(N,height,maxLen);//得到每个导弹对应键值的拦截数量 for (int i = 0; i < maxLen.length; i++) { if(maxLen[i]>Max){ Max = maxLen[i]; } } System.out.println(Max); } private static void f(int n, int[] height, int[] maxLen) { for (int i = 0; i < n; i++) { maxLen[i] = 1; for (int j = 0; j < i; j++) {// int p = 1;// if(height[i]<=height[j]){// p = maxLen[j]+1;// }// if(p>maxLen[i]){// maxLen[i] = p;// } if((height[i]<=height[j])&&(maxLen[j]+1>maxLen[i])){ maxLen[i]=maxLen[j]+1; } } } }}
C语言：
#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; }