|
试题描述
|
|
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算这套系统最多能拦截多少导弹?该导弹数量不超过100个。
|
|
输入
|
|
一行有若干个整数，表示依次飞来导弹的高度。两数之间用一个空格分隔。
|
|
输出
|
|
一个数，表示该系统最多能拦截的导弹。
|
|
输入示例
|
|
389 207 155 300 299 170 158 65
|
|
输出示例
|
|
6
|
|
其他说明
|
|
数据范围见题目中的描述。
|
1 #include <iostream> 2 3 using namespace std; 4 int a[101],b[101]={1}; 5 int main() 6 { 7 int i,j,n,t,cnt=0; 8 while(cin>>t) 9 { 10 a[++cnt]=t; 11 } 12 b[1]=1; 13 for(i=2;i<=cnt;i++) 14 { 15 for(j=1;j<i;j++) 16 { 17 if(a[j]>=a[i] && b[j]+1>b[i]) b[i]=b[j]+1; 18 } 19 //cout<<b[i]<<endl; 20 } 21 int maxn=0; 22 for(i=1;i<=cnt;i++) 23 if(b[i]>maxn) maxn=b[i]; 24 printf("%d",maxn); 25 //system("pause"); 26 return 0; 27 }
不是很难，简单说一下吧：用一个数组储存当前可拦截到的最大值，然后再依次判断他前面的导弹高度是否高于他。如果是，且那个导弹所储存的拦截数量+1（当前位置）>当前位置（不一定是1，可能之前也赋过值），就替换。直到找到最大的一列。
（其实就是最长不上升子序列）
原文：http://www.cnblogs.com/YXY-1211/p/5267967.html
