BZOJ 5161 最长上升子序列

发布于 2018-02-23  302 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=5161

题意:现在有一个长度为 n 的随机排列,求它的最长上升子序列长度的期望。为了避免精度误差,你只需要输出答案模 998244353 的余数。


虽然题意里有个期望,但是没用,只能计数。

这题状压做法挺神的... 还有更神的杨表做法还不会... 过几天去看看能不能看懂...

考虑记录状态,排列状态太多了,没法记,但是我们实际 dp 的时候用到了一个数组 \(h\) ,其中\(h_i\) 表示不大于\(i\) 的数字结尾的 LIS 的长度,实际上只有这个信息是对 LIS 有用的。只需要统计满足\(h\) 的排列的个数即可。

转移的时候考虑目前有一个大小为 i 的排列\(P_i\),如果这个排列存在一个以不大于\(j\) 的数字结尾的 LIS,那么我们可以进行如下操作:

令这个排列中大于\(j\) 的元素均加一,将\(j+1\) 接到序列的最后,这样我们得到了一个长度为\(i+1\) 的排列,且这个排列拥有一个以\(j+1\) 结尾的长度加一的 LIS,更新新状态即可。

这样转移的问题就解决了,如果我们能确定状态数,就可以知道复杂度了,显然\(h\) 是递增的,因为多了一个数只会让 LIS 长度加一或者不变,也就是说\(h_i-h_{i-1}\) 非 0 即 1。

所以状态数是\(O(2^{n-1})\) 的。

附打表代码:

 


一个非常弱的准退役OIER