洛谷P1020题解

sunyizhe · 2022-08-19 12:31:22 · 题解

这题是道 LIS 好题！本人调了两天两夜才对……

题目传送带

一、 题意

1. 第一问

其实是要先把数组反过来，再求数组的 \operatorname{LIS} （即最长上升子序列）。LIS 是由 DP 实现。设 a_i 为序列第 i 项。对于任意的 i，定义 f_i 是以 a_i 结束的最长上升子序列的长度，显然问题的解为 f_n。

不妨假设，已求得以 a_1，a_2，\cdots，a_j 结束的最长上升子序列的长度分别为 f_1，f_2，\cdots，f_j。其中 f_1 = 1。

那么对于 a_i，其中 j<i，若 a_j<a_i，则以 a_i 结束的最长上升子序列的长度为 f_j+1，显然 a_i 结束的最长上升子序列的长度

其中 1 \le j \le i-1，a_j<a_i。 更新公式中每次都得重头遍历整个 f_i，所以时间复杂度为 O(n^2)。

部分代码：

reverse(a+1,a+n+1);//倒着求LIS
fill(f+1,f+n+1,1);//初始化f
for(int i=2;i<=n;i++)//n个阶段
{
    f[i]=max(f[i-1]+a[i],a[i]);//两种决策
    ans=max(ans,f[i]);//取最大值
}
cout<<ans<<endl;

2. 第二问

需要用到 \operatorname{Dilworth} 定理。即将一个序列分成若干个最长不升子序列的个数就是最长上升子序列的长度。其实就是第一问反着做。 代码与上方一样，只需把 ans 初始化成 0。

二、优化

上方算法在 n \le 10^5 的数据规模中超时，无法通过后 10 个点。

定义数组 len[N] 记录所有长度为 x 的上升子序列中尾元素的最小值。