拦截导弹

思路

首先先捋清一下题意：有若干发炮弹，拦截系统拦截的导弹的高度必须是递减的，那这道题就变成了最长下降子序列了，和下面一道题类似，用动态规划求解。

用 dp[i] 表示以 i 结尾的子序列的最长长度，那么状态转移方程为：

#include<iostream>
#include<vector>

using namespace std;


int main(){
    int k;
    while(cin >> k){
        vector<int> height(k, 0);
        for(int i = 0; i < k; i ++)
            cin >> height[i];
        vector<int> dp(k, 1);
        int ans = 0;
        for(int i = 0; i < k; i ++){
            for(int j = 0; j < i; j ++)
                if(height[j] >= height[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            ans = max(ans, dp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}