昨天C++课上留了三道题，除了C语言本身外都涉及了一些算法。其中第二个问题是这样的：
拦截导弹
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。
输入
第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），
第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。
输出
输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。
样例输入
8
300 207 155 300 299 170 158 65
样例输出
6
课堂上没搞出来。老师说用到了动态规划。好吧，高中没学过信息学竞赛。不过没关系，回去翻了翻《算法导论》，基本算弄明白了。其实就是求一串数的最长递减子序列。
问题关键在于，可能的情况组合很多，不适合穷举。所以要利用动态规划（很适合这类问题）。动态规划把问题分成很多子问题，而子问题之间又有关系。子问题不是相互独立的，子问题可能有重叠，全局最优解由子问题的最优解构成（最优子结构性质）。这和分治法（典型的比如归并排序）不一样。
动态规划的基本想法在于：
- 描述最优解结构，就是说最优解是什么样子的，符合什么条件。
- 递归定义最优解的值。也就是写出状态方程。其中一般需要特别考虑初始条件。
- 自底向上计算最优解的值。
- 由计算的值构造最优解（在这题里没要求，到第三部求出序列长就行了）。
其中，问题设计时最关心的就是第二步。以下的步骤是必不可少的：
- 阶段划分。
- 确定状态变量。当前状态变量是由之前阶段的某个状态转移来的。当前状态是对之前所有状态的完整总结。当前这个状态之后的选择只受当前最优决策序列的影响（无后效性）。
- 写状态转移方程。也就是确定如何从之前状态得到本阶段的状态。
- 找边界条件（开始和终止的条件）。
比如说，这个问题中要拦第i个导弹。截止到第i个导弹的最长拦截序列肯定包含了前面i-1个导弹中最长的序列。如果不是这样，我们求出的截止到第i个导弹的拦截序列就不是最长的了。我们用数组D[i]把截止到第i个导弹的最长拦截序列长度存起来。最后计算完i=k（导弹总数）时，整个问题的答案就是数组D[i]的最大值。
如果用一个数组，把前一个最优解对应的导弹编号存下来，最后还可以把被击落的导弹高度按编号输出。
代码：
/*
设数组A存放导弹高度，D[i]是高度为A[i]是的最优解，S用于记录最优解中导弹被击落的次序
最优解结构：设在第k个数处的最优解为D(k)。设当前位于第i个数，则在第i个数处的
最优解D(i)为：在i之前拦下导弹最多的方法的解D(j)加上1。（因为把第i
个也打下来了，所以加上1）。当然还要保证A[i]<=A[j]
递归解：D(i)=D(j)+1。j是数组A中位于A[i]左侧，且大于等于A[i]的所有数中D值最大的
那个。如果A[i]左侧没有找到大于等于它的数，则D[i]=1。
状态转移方程：D(i)=max{D(j)+1} (0<=j<i<k)
D(0)=1
最终结果：找到数组D中最大的数，这个数就是结果。
*/
#include <cstdio>
int main(){
int k;
scanf("%d", &k);
int A[k], D[k], S[k];
for(int i=0; i<k; i++){
scanf("%d", &A[i]);
D[i]=0;
}
D[0]=1;
for(int i=1; i<k; i++){
bool found=false; //是否找到i之前的最优解
int last_good_solve=D[0];
int good_position=0;//最优解的下标和值
for(int j=0; j<i; j++)
if(A[j]>=A[i] && D[j]>=D[good_position]){
last_good_solve=D[j];
good_position=j;
found=true;
}
if(found){
D[i]=1+D[good_position];
S[i]=good_position;
}
else {
D[i]=1;
S[i]=good_position;
}
}
int result=0; int go_back;//用于向前找被击落的导弹
for(int i=0; i<k; i++){
if(D[i]>result){
result=D[i];
go_back=i;
}
}
printf("%d\n", result);
for(int i=0; i<result; i++){
printf("%d ", A[go_back]);
go_back=S[go_back];
}//逆序输出被击落导弹的高度
}