题解 | 拦截导弹，简单动态规划

简单动态规划：最长递增子序列(不连续)的翻版，最长递减子序列。从后向前即可。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    int res;
    while (cin >> n) { // 注意 while 处理多个 case
        vector<int> missiles(n);
        for(int i=0;i<n;i++){
            cin>>missiles[i];
        }
        vector<int>DP(n,1);
        res=1;
        for(int i=n-2;i>=0;i--)
            for(int j=n-1;j>i;j--){
                if(missiles[i]>=missiles[j])
                    {
                        DP[i]=max(DP[i],DP[j]+1);
                        if(res<DP[i]) res=DP[i];
                    }
            }
        cout<<res;
    }
}
// 64 位输出请用 printf("%lld")