Important

【这篇题解放在这里是用来测试Gmeek整体渲染效果的，题解内容是半年前随便写的，正确性、严谨性、规范性没有保证，仅供参考（？）】

题目大意：对于一个数列，求出其最长不上升子数列的长度，以及至少能用几个最长不上升子序列覆盖整个数列。

思路

$O(n^2)$ 朴素做法

对于第一个分任务，考虑线性动态规划，寻找状态方程。

记以原数列（长度为 $n$ ）第 $i$ 项为结尾的最长不上升子数列的长度为 $dp_{i}$ ，最终目的是求出 $\displaystyle \max_{i = 1,..,n} dp_{i}$ 。

首先考虑 $dp_{i}$ 的值会受到什么影响？

对于 $i$ 前面的所有项 $j$ ，只要 $arr_{i} \leqslant arr_{j}$ ，说明 $arr_{i}$ 可以加在 $arr_{j}$ 后面，构成一个更长的不上升子数列，此时 $dp_{i}$ 有可能受到影响成为 $dp_{j} + 1$ ，也有可能因为目前的 $dp_{i}$ 已经足够大而不受影响。

考虑到这是唯一会改变 $dp_{i}$ 的情况，可以据此得到状态方程：

$$ dp_{i}=\max (dp_{i}, dp_{j}+1) ,\quad \text{for all } j < i \text{ and } arr_{i} \leqslant arr_{j} $$

根据状态方程写出实现第一个任务的代码，时间复杂度为 $O(n^2)$ ：

for (int i = 0; i < n; dp[i++] = 1) {}	// 设置每项初始值为 1

for (int i = 1; i < n; i++)
	for (int j = 0; j < i; j++)	// 对于每个 i ，遍历在它之前的所有值
		if (arr[i] <= arr[j])	// true: arr[i] 可以接在以 arr[j] 结尾的不上升子数列后面，长度 + 1
			dp[i] = max(dp[i], dp[j] + 1);	// 长度可能改变为 dp[j] + 1 ，也可能依旧是 dp[i] 自身

对于第二个分任务，事实上可以转化为求最长（递增）子序列的长度。因为每个不上升子数列中的元素在原序列中是不上升的，所以如果我们能找到最长的递增子序列，那么每个递增子序列中的元素必须属于不同的不上升子数列。（严格证明详见 Dilworth 定理 from OI_Wiki ，反正我看不懂）

所以把上述代码的 $arr_{i} \leqslant arr_{j}$ 变个符号（ > ）就能解决问题了。

$O(n \log n)$ 优化做法

上面的代码只能 $AC$ 前 $50 \%$ 的数据，以下是针对后 $50 \%$ 的数据的 贪心 + 二分 做法（原理写在注释中）：

// 最长单调不上升串
vector<int> dp1;	// dp1 是一个不上升栈
for (int num : arr)
{
    if (dp1.empty() || num <= dp1.back())	// 若当前元素 <= dp1 的最后一个元素，则直接添加到栈的末尾
        dp1.push_back(num);
    // 否则【找到第一个小于当前元素的位置】并替换，保持数组的降序特性同时，尽可能使末元素足够小
    // 这样这串序列的长度就更有可能延长，就能够实现最长不上升子序列
    // * 注意 dp1 的内容本身并不是这个最长不上升子序列，它只能表示长度！
    else
    {
        auto it = upper_bound(dp1.begin(), dp1.end(), num, greater<int>());	// 【找】
        *it = num;	// 换
    }
}
// 由于 dp1 始终保持降序，并且每次操作都尽可能延长序列的长度，因此最终 dp1 的长度就是最长不上升子序列的长度

// 同理找最长严格递增串，只需要改动下面的两处地方：
// if (dp2.empty() || num > dp2.back())
// auto it = lower_bound(dp2.begin(), dp2.end(), num);

这样就得到了完全 AC 代码