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 即可，卡掉其他的解法。