总时间限制: 10000ms 内存限制: 65536kB

描述

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。

输入

输入有两行，
第一行，输入雷达捕捉到的敌国导弹的数量k（k ≤ 25），
第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。

输出

输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。

样例输入

8
300 207 155 300 299 170 158 65

样例输出

思路

找子问题

与最长升序子序列相反, 本题是求最长降序子序列.

有N个导弹来袭, 求以 a (k = 1, 2, 3… N)为拦截终点的最长下降子序列为我们的子问题.

确定状态

子问题只有一个变量: 拦截位置. 因此序列中位置k就是状态.

而状态k对应的值, 就是以 a 为终点的最多拦截导弹数.

状态转移方程

设maxNum(k)表示以a为终点的最长下降子序列的长度(最多拦截数), 那么:

$POJ 2945 拦截导弹 - 图1$ %20%3D%20%0A%5Cbegin%7Bcases%7D%0A1%2C%20%26%20k%20%3D%201%20%5C%5C%0Amax%5C%7B%20%5C%20maxNum(i)%20%5C%7D%5C%20%2B1%2C%20%26%20i%20%5Cin%20%5B1%2C%20k)%20%E4%B8%94%20a_i%20%3E%20a_k%20%E4%B8%94%20k%20%5Cne%201%0A%5Cend%7Bcases%7D%0A#card=math&code=maxNum%28k%29%20%3D%20%0A%5Cbegin%7Bcases%7D%0A1%2C%20%26%20k%20%3D%201%20%5C%5C%0Amax%5C%7B%20%5C%20maxNum%28i%29%20%5C%7D%5C%20%2B1%2C%20%26%20i%20%5Cin%20%5B1%2C%20k%29%20%E4%B8%94%20a_i%20%3E%20a_k%20%E4%B8%94%20k%20%5Cne%201%0A%5Cend%7Bcases%7D%0A)

maxNum(k)的值, 就是在 a 左边, 终点数值大于 a, 且长度最大的那个下降子序列的长度再加1.

因为 a 左边任何终点大于 a 的子序列, 加上 a 后能形成一个更长的下降子序列.

代码

#include <iostream>
#include <algorithm>
using namespace std;
int number;     // number of missile
int maxNum[30];
int missile[30];
int main() {
    cin >> number;
    for(int i = 1; i <= number; i++) {
        cin >> missile[i];
        maxNum[i] = 1;
    }
    for(int i = 2; i <= number; i++) {
        /* 每次求以第i个为终点的最长下降子序列的长度 */
        for(int j = 1; j < i; j++) {
            /* 检查以第j个数为终点的最长下降子序列 */
            if( missile[j] >= missile[i] ) 
                maxNum[i] = max(maxNum[i], maxNum[j]+1);
        }
    }
    cout << *max_element(maxNum+1, maxNum+number+1) << endl;
    return 0;
}