动态规划还是ACM的难点啊，我正在想怎么能有点突破呢，可否给点意见。
编程之路定要走完……
回复 10楼 czz5242199
呵呵，雪的描述过于简单，但其实你俩的算法本质上是完全一样的，甚至得到的方案都完全一致（每套系统拦截哪些导弹）。虽然雪的算法没有错，但我猜雪是凭直觉构建的算法，并没有对这个模型做过深入的分析吧？
雪的每次都从头到尾扫描导弹序列的过程其实已经暗含了小曹分析中找出“大于等于这枚导弹高度中最低的系统”的过程。
你俩算法的不同之处在于搜索的方向不同。
如果建一个平面坐标系，横坐标表示导弹来袭的序列，纵坐标表示导弹的高度。
将坐标系中同一套系统拦截的导弹的点按顺序连接，则你们（当然也包括我的）的算法都将形成一簇大致从左向右延伸且不相交的线。线的数量即需要配备的拦截系统的数量。
在形成这簇线的过程中，雪的算法是从最底的一条线开始一条一条由低到高形成，而小曹的算法而是从左到右逐一将点加入到线簇当中。
至于我的算法，我的思维好像和大多数人不同呵呵，是从右到左将点加入线簇当中。
这些算法的理论时间复杂度是相同的，都是O(n * m)。其中n是导弹的数量，m是最少需要的拦截系统的数量。
当然，这是都用顺序检索的分析结果。
当小曹在检索“大于等于这枚导弹高度中最低的系统”的过程使用二分法，则小曹的算法时间复杂度将降到O(n * log(m))。
当雪使用链表来处理检索过程，则可以提高一些效率，但代码的复杂度增加，理论时间复杂度不变。
在空间复杂度上，雪的算法为S(n)，而小曹的算法为S(m)。m <= n
总体说来，小曹的算法更优一些。
最后送上我的代码。这该算是我实现的小曹的算法。我之前的算法因为是从右向左，虽然在时间复杂度上与小曹的相同，但时间复杂度是S(n)。呵呵，从这点上讲略逊于小曹的算法。
程序代码：#include<stdio.h>
int main()
{
int a[40000], n, p, i, t;
for(; scanf("%d", &n) != EOF; printf("%d\n", p))
for(p = 0; n-- && scanf("%d", &t); a[i < p ? i : p++] = t)
for(i = 0; i < p && a[i] < t; i++);
return 0;
}
