题解 | #拦截导弹#

#include <iostream>
using namespace std;

/*
最长递减序列
*/
int missile[30];
int dp[30]; //dp[i]表示以i位置结尾的最长递减序列的长度

int main() {
    int k;
    scanf("%d", &k);
    for(int i = 0; i < k; i++){
        scanf("%d", &missile[i]);
    }
    fill(dp, dp + 30, 1); //给dp赋初值1
  
    for(int i = 1; i < k; i++){ //遍历missile数组，找到比当前missile[i]要大的高度
        for(int j = 0; j < i; j++){
            if(missile[i] <= missile[j]){ //注意这里高度相同也能打到
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
    }
  
    int max = 0;
    for(int i = 0; i < k; i++){ //遍历dp数组，找到最大值
        max = max > dp[i] ? max : dp[i];
    }
    printf("%d\n", max);
}
// 64 位输出请用 printf("%lld")