[状压] P4484 [BJWC2018] 最长上升子序列

· · 个人记录

考虑怎么生成排列，有一种套路：将元素从小到大依次插入序列，比如 132 插入 4 就有 4132,1432... 共四种情况。

好处是新插入的元素一定大于先前所有元素，相当于多了一条性质，这在 插入法dp 里也是很有用的。

容易发现，在下标 j 右边插入新元素 i 后，以 1...i-1 结尾的 \rm LIS 长度都不会变，而 i 结尾的 \rm LIS 长度就是 LIS_j+1！

但是还是需要枚举全排列，所以必须对它进行压缩。显然 LIS_i-LIS_{i-1}\le1，那么不妨对其差分，差分数组 d_i=LIS_i-LIS_{i-1}，再对差分数组状压，f_S 记为满足差分数组压缩为 S 的排列数量。

结合上述讨论，不难得到插入新元素 i 后差分数组的变化，这相当于在 j 右边插入一个 1，并且将原数组中离 j 最近的且在 j 右边的 1 变成 0。

有点扯淡？举个例子：在原排列中下标 2 的后面插入新元素，假如原来差分数组是 11001，那么就会变成 100101。位运算处理一下即可。

复杂度 O(n^22^n)，但是这道题 n\le28，直接写过不了怎么办？

打表啊！ 提交记录