题解 | #拦截导弹#

//最长递减子序列问题，和LIS没什么区别
#include "stdio.h"
using namespace std;
int n;
int missile[26];//记录导弹高度
int dp[26];//记录最长递减子序列长度

void Init(){
    dp[1] = 1;int max;
    for (int i = 2; i <= n; ++i) {//动态规划求最长递减子序列
        max = 1;
        for (int j = 1; j <= i; ++j) {
            if (missile[j] >= missile[i]){
                if (dp[j] + 1 > max)
                    max = dp[j] + 1;
            }
        }
        dp[i] = max;
    }
}

int main(){

    while (scanf("%d",&n)!=EOF){
        for (int i = 1; i <= n; ++i) {
            scanf("%d",missile+i);
        }
        Init();
        int max = 0;
        for (int i = 1; i <= n; ++i) {//找到dp中最大值(最长递减子序列长度)
            if (dp[i] > max)
                max = dp[i];
        }
        printf("%d\n",max);
    }
}