题目链接

改题目分为两个问题

第一个就是求最长的不上升子序列的长度

第二个是求原序列最少可划分为多少不上升子序列

第二个问题根据dilworth定理，求可划分的最少的不上升子序列等于求最长的上升子序列的长度。所以该题的本质上就是求一个最长的上升子序列和一个最长的不上升子序列。而对于求一个单调上升子序列的最长长度，如果按照线性dp的方式（如下）

for(int i = 1; i <= n; i ++){
	dp[i] = 1;
	for(int j = 1; j < i; j ++){
    	if(a[i] > a[j])	dp[i] = max(dp[i], dp[j] + 1);
    }
}

其时间复杂度位O(n * n)，显然在本题中是会超时的，所以需要采取贪心的方式来解。

我们不妨开一个数组len[i]维护当子序列的长度为i时，该子序列的最后一个元素的值。根据贪心的思想，最后一个元素的值应该尽可能的小，并且len数组由于记录的为最后一个元素的值，所以是单调递增的。

通过

for(int i = 0; i < n; i ++){
    int idx = lower_bound(len, len + n, a[i]) - len;
    len[idx] = a[i];
}

的方式对len进行维护，这样len数组中的值就为长度为i的递增子序列的最后一个元素的值（最优解），所以只需要找最后一个i使得len[i]被维护过，即为最长上升子序列。

对于求解最长的不上升子序列的问题，可以先将数字进行翻转，这样即为求解最长的不下降子序列的问题，和求解最长的上升子序列问题的唯一不同的点就是当a[i] = len[i]时，要维护len[i + 1]，所以要用的是upper_bound而不是lower_bound。

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int a[100010];
int len[100010];
int n, ans1, ans2;
int main(){
    int x;
    while(cin >> a[n]){
        n += 1;
    }
//     cout << n << endl;
    fill(len, len + n, INF);
    for(int i = 0; i < n; i ++){
        int idx = lower_bound(len, len + n, a[i]) - len;
        len[idx] = a[i];
    }
    for(int i = n - 1; i >= 0; i --){
        if(len[i] != INF){
            ans1 = i + 1;
            break;
        }
    }
    reverse(a, a + n);
    fill(len, len + n, INF);
    for(int i = 0; i < n; i ++){
        int idx = upper_bound(len, len + n, a[i]) - len;
        len[idx] = a[i];
    }
    for(int i = n - 1; i >= 0; i --){
        if(len[i] != INF){
            ans2 = i + 1;
            break;
        }
    }
    cout << ans2 << endl << ans1 << endl;
}