$\LARGE\color{orange}{刷题日记(算法提高课)}$

第一问就是求从左向右求一遍最长下降子序列，等价于从右往左求一遍最长上升子序列，直接用 LIS 的代码解决，重点是第二问

第二问实际要求的是该序列中最少有多少个下降子序列

不失一般性地，假设我们当前遍历到的数是 $x$ ，在 $x$ 前面的数已经组成了多个下降子序列

由于我们希望最后得到的子序列个数最少，因此我们希望能过将 $x$ 接在前面的某个子序列的后面，如果实在做不到，就另开一个以 $x$ 为结尾的子序列

那么我们现在需要考虑的是将 $x$ 接在哪个子序列的后面更好

直觉上来说，为了能便于后面的数也同样能过接在前面的某个子序列后面，子序列递减的速度应该尽可能的慢

因此，子序列结尾的数应当于 $x$ 的差距尽可能的小，也就是将 $x$ 接在一个比它大的数当中最小的一个数的后面

下面我们该贪心思路的证明：

我们设贪心得到的子序列个数为 $A$ ，最优解的子序列个数为 $B$

只要能够证明 $A\ \ge\ B,\ A\ \le\ B$， 就能证明 $A\ =\ B$

由于 $B$ 所表示的是最优解的子序列个数，因此有 $B\ \le\ A$

我们设贪心解法与最优解法所构造的子序列当中，第一个不同的数为 $x$ ，即 $x$ 之前的数构成的子序列二者都相同

由于贪心解法将 $x$ 接在一个最小的比它大的数后面，因此贪心解法 $x$ 前面的数一定小于等于最优解法 $x$ 前面的数

在此，我们可以通过交换 $x$ 以及 $x$ 后面的数，使得在 $x$ 这个位置上，贪心解法能过转换为最优解，并且总子序列个数不变

同理，对于任意一个数，我们都可以将贪心解法转换成最优解法，因此有 $A\ \le\ B$ （我们只能确定 $A$ 一定不可能大于 $B$）

证明贪心问题时，我们通常会去证明 $A\ \ge\ B,\ A\ \le\ B$ ，方法通常是调整，即考虑能否将贪心解法调整为最优解法

在代码的实现上，我们用 $g[i]$ 表示各个组当中结尾的数，由于我们每次都会将 $a[i]$ 接在最小的比它大的数后面，而对于比它小的数则忽视，因此可以保证 $g[i]$ 一定单调递增

有了这一性质，直接从前往后遍历 $g[i]$ （也可以用二分），找到第一个比 $a[i]$ 大的数将其替换掉即可，最后 $g[i]$ 数组的长度就是答案

• $g[i]$ 数组表示的是下降子序列的结尾元素，该数组本身是单调递增的
  这是因为如果要另开一组，那么当前元素一定会比所有子序列的结尾元素要大，因此数组必然递增

完整代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[N], f[N], g[N];
int n;

int main()
{
    while(cin >> a[n]) n++;
    int ans = 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);
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        int idx = 0;
        while(idx < cnt && g[idx] < a[i]) idx++;
        g[idx] = a[i];
        if(idx >= cnt) cnt++;
    }
    cout << cnt << endl;
    return 0;
}