要求：

分析:

证明：

结论：

更新：
$\cal{P.S}$:

这里有个疑问：

如果从贪心的思想来想，把当前数 x 放到结尾 最小的>= x 的子序列中，可以得到最小的序列数量。
但是如果从做法的角度考虑，类比 LISII 的做法，应该是让 g[] 的长度最大，这不就相当于让g[]结尾的序列数量最大吗?

Answer

g[]的长度是系统的数量。其中g[i]表示第i个系统结尾元素。
一个系统的单调递减的，因此如果出现了一个新的系统，代表新的系统结尾元素 a[i]>上一个系统结尾元素a[j] , 因此g是单调递增的。相当于求序列a的LIS。
要让系统数量最小，就是让g[]长度最小。

代码：

1. 用o($\cal{n^2}$)求最长不上升子序列

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int a[N], f[N], g[N];
int n; 

int main()
{
    while(cin >> a[n])n++;
    int len1 = 1, len2 = 1;
    int res = 0;
    for(int i = 0; i < n; ++i)
    {
        f[i] = 1;
        for(int j = 0; j < i; ++j)
            if(a[j] >= a[i])f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    for(int i = 0; i < n; ++i)
    {
        int l2 = 1, r2 = len2;
        while(l2 < r2)
        {
            int mid = l2 + r2 + 1>> 1;
            if(g[mid] < a[i])l2 = mid;
            else r2 = mid - 1;
        }
        g[r2 + 1] = a[i];
        len2 = max(len2, r2 + 1);
    }
    //cout << len1 - 1 <<endl;
    cout << res <<endl;
    cout << len2 - 1<< endl;
    return 0;
}

1. 用o($\cal{n * log_n}$)求最长不上升子序列

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int a[N], f[N], g[N];
int n; 

int main()
{
    while(cin >> a[n])n++;
    int len1 = 1, len2 = 1;
    int res = 0;
/*    for(int i = 0; i < n; ++i)
    {
        f[i] = 1;
        for(int j = 0; j < i; ++j)
            if(a[j] >= a[i])f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }*/
    for(int i = 0; i < n; ++i)
    {
        int l = 1, r = len1;
        while(l < r)
        {
            int mid = l + r + 1>> 1;
            if(f[mid] >= a[i])l = mid;
            else r = mid - 1;
        }
        f[r + 1] = a[i];
        len1 = max(len1, r + 1);
/*        cout << r <<' ';
        for(int j = 1; j <= len1; ++j)
            cout << " " << f[j] <<" ";
        cout <<endl;*/


        l = 1; r = len2;
        while(l < r)
        {
            int mid = l + r + 1>> 1;
            if(g[mid] < a[i])l = mid;
            else r = mid - 1;
        }
        g[r + 1] = a[i];
        len2 = max(len2, r + 1);
    }
    cout << len1 - 1 <<endl;
   // cout << res <<endl;
    cout << len2 - 1<< endl;
    return 0;
}