题解 | #拦截导弹#

等价于求两个问题：

问题1： 求最长不增（小于等于）子序列的长度

方面就是 线性dp

问题2： 求 最少可以划分出不增（小于等于）子序列的个数

#include <iostream>
#include <set>
using namespace std;
const int N = 1010;
int h[N];
int dp[N];   //dp[i]表示 长度为i的 子数组的 最长不增（小于等于）子序列的长度。

int main() {
    
    int n;
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> h[i];
        dp[i] = 1;  //给dp赋 初值
    }
    int res1 = 1;
    //找给定 高度数组中的最长下降子序列
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<i;j++){
            if(h[i]<=h[j]){
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
        if(dp[i]>res1) 
            res1 = dp[i];

    }
    cout << res1 << endl;
    // 在高度数组中， 看可以 划分出最少多少个 下降子序列，子序列的个数最少，说明一个下降子序列尽可能长 ？
    /*算法：
        1. 从前往后扫描， 当前高度<序列上一个高度，就加入序列，直到末尾
        2. 到达末尾后，进行下一遍扫描，流程和步骤1 一样
        3. */
    set<int> st;

    int last;  //序列上一个值
    int res2 = 0;
    while(st.size()!=n){
        int isFirst = 1;   //一个for形成一个 序列，当是某序列中第一个 数字时，不在需要它<=last了 
        for(int i = 1;i<=n;i++){
            if(isFirst && st.count(i)==0){
                st.insert(i);
                last = h[i];
                isFirst = 0;
            }
            else if(st.count(i)==0 && h[i]<=last){
                st.insert(i);
                last = h[i];
                isFirst = 0;
            }
        }
        res2 += 1;
    }
    cout << res2 << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")