闫式dp分析法

/*
    题目分析 :  
               1) 第一问 : 显然是问的最长下降子序列   那么求法基本和前面几道题一致 (请看前面的题解)


               2) 第二个，问最少需要多少个下降序列才可以把整个序列包括完
                   那么应该有两种情况 :  
                        第一种  ： 当前值 h[i] 可以被加入到已经存在的下降字序列中 条件下降子序列的末尾值必须 > h[i]
                        第二种  :  当前 h[i] , 不能被加入到已经存在的序列中，那么应该新添加一个序列

                根据上述分析 : 我们不需要记录每一个序列的所有值，子需要记录一下   已经存在的下降序列的末尾元素即可     



*/
#include <iostream>
#include <algorithm>


using namespace std;
const int N = 1010;
int f[N] , h[N] , up[N];

int main() {
    int cnt = 0;
    while (cin >> h[cnt]) cnt ++;

    int res = 0;
    for (int i = cnt - 1 ; i >= 0 ; i -- ) {
        f[i] = 1;
        for (int j = cnt - 1 ; j > i ; j -- ) 
            if (h[i] >= h[j] ) f[i] = max(f[i] , f[j] + 1);
        res = max(res,f[i]);
    }
    cout << res << endl;

    int ans = 0 ;
    for (int i = 0 ; i < cnt ; i ++ ) {
        int k = 0;
        while (k < ans && up[k] < h[i]) k ++;
        up[k] = h[i];
        if (k >= ans) ans ++;
    }
    cout << ans;
}