题解 | 拦截导弹

//这就是普通的最长递减子序列问题  ，用动态规划

#include<iostream>
#include<math.h>
using namespace std;
int nums[26];
int dp[26];  //dp[i][j]表示从i
int main(){
    int k;
    cin>>k;
    int maxl=0;
    for(int i=1;i<=k;i++){
        cin>>nums[i];
        dp[i]=1;
    }
    for(int i=1;i<=k;i++){
        for(int j=1;j<i;j++){
            if(nums[i]<=nums[j]){
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
    }
    for(int i=1;i<=k;i++){
        maxl=max(maxl,dp[i]);
    }
    cout<<maxl;
    return 0;
}


/*
8
300 207 155 300 299 170 158 65
*/