dp 套 dp 一般有三种形式:
-
暴力搜出一种东西的状态,发现数量不大,建出自动机开始跑;
-
有关字符串的匹配问题,例如 kmp 或 AC 自动机上;
-
有关 LIS 问题的可以使用一种特殊的内层 dp 优化状态。
前两个没什么好讲的,讲一下第三个。
记 \(f_i\) 为 \(1\sim i\) 的 LIS 长度(不一定要 \(i\) 结尾)。
发现 \(f_i\le f_{i+1}\),同时也有 \(f_{i+1}-1\le f_i\)。
所以 \(f_{i+1}-f_i\in\{0,1\}\),于是可以状态压缩这个差分数组。
但是这样子做需要从小到大加数,每次在加的位置改为 \(1\),后面第一个 \(1\) 变成 \(0\)(如果没有就不管)。
这样可以把 LIS 压缩成 \(2^n\)。
例题
HHHOJ #1255. 「NOIP 2023 模拟赛 20230716 D」拳击比赛 加强版
直接这么压缩 LIS 即可,卡掉其他的解法。