题目链接：https://vjudge.net/problem/HDU-1257点击打开链接
最少拦截系统
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 54893 Accepted Submission(s): 21495
Problem Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
Source
浙江工业大学第四届大学生程序设计竞赛
做题感悟：
当然每次写博客题解的时候，都要先吐槽一下。我都怀疑那长江是不是捏自己一把才形成的，水到无可救药。那么来看看我是怎么水的，首先拿到这道题的时候，当然是在VJ比赛啦。吼，中文题还有这么多人AC，emmm，简单题，好的开始读题，呀拦截系统是什么，题目给了数据范围30000，嗯这个范围不大。要求输出导弹最少要配备多少套这种导弹拦截系统？OK，我懂了。But,导弹拦截系统的高度没给呀，要用动态规划（学长早晨刚刚授课了动态规划）？那我来套套动态规划的解题步骤，分析看看。
Oh,my god!你能看到这里我也是很佩服你，因为我都已经受不了自己了，先是读题不仔细，又要自己望文生义。可能我的脑子在养金鱼。But,我不想放弃自己，来，扶我起来，我还能学。
言归正传：
解题思路:
1. 我们可以从中获得的所有信息如下：
从读题开始，我们可以获得的信息：拦截系统的第一发炮弹能够到达任意的高度，但是以后的每一发炮弹都不能超过（可以小于等于）前一发的高度。
接下来是输入要求：1.导弹的总个数和飞来的高度；2.雷达给出的高度不超过30000.
输出要求：最少配备多少拦截系统。（最少配备多少能够完成拦截全部导弹的任务。）
2.因此我们每选择一个导弹拦截系统，都是一个连续的下降序列，故将其最小值（即：拦截最后一次的值）存入数组，每次都判断新的数据是否小于等于之前的数据，一直如此往下刷新遍历即可。
AC代码：
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int h[1005]; //存储导弹拦截系统拦截高度
int main()
{int n,i,j;int height;while(~scanf("%d",&n)){memset(h,0,sizeof(h));int ans = 1;scanf("%d",&h[1]);for(i = 2;i <= n; i++){scanf("%d",&height);for(j = 1;j <= i; j++){if(height <= h[j]) //每次找最小的进行更新{h[j] = height;break; //一旦找到符合条件的就跳出循环，执行下一次的比较.}}if(j > i){ans++;h[ans] = height;}}printf("%d\n",ans);}return 0;
}//存储导弹拦截系统拦截高度
int main()
{int n,i,j;int height;while(~scanf("%d",&n)){memset(h,0,sizeof(h));int ans = 1;scanf("%d",&h[1]);for(i = 2;i <= n; i++){scanf("%d",&height);for(j = 1;j <= i; j++){if(height <= h[j]) //每次找最小的进行更新{h[j] = height;break; //一旦找到符合条件的就跳出循环，执行下一次的比较.}}if(j > i){ans++;h[ans] = height;}}printf("%d\n",ans);}return 0;
}*注解：如果你还是没有看懂，下面我运行了其他样例来帮助你理解：
添加输出每次存留下来的数组数值后的代码：（就是白色那一部分）
while(~scanf("%d",&n)){memset(h,0,sizeof(h));int ans = 1;scanf("%d",&h[1]);for(i = 2;i <= n; i++){scanf("%d",&height);for(j = 1;j <= i; j++){if(height <= h[j]){h[j] = height;break;}}if(j > i){ans++;h[ans] = height;}}printf("%d\n",ans);
for(i = 1;i <= n; i++)printf("%d***\n",h[i]);} for(i = 1;i <= n; i++)printf("%d***\n",h[i]);}
由此运行结果可知：最后一个高度150并没有重新加一个导弹拦截系统，而是直接用地一个导弹拦截系统的最小值：155来进行拦截，这里就充分的体现了选用最少的拦截系统的思想（贪心的思想）。
相类似的题目：HDU-1722