很神奇的状态。。。。。。
很难想象这是一个人能在考场上想到的状态。
对于一个排列 \(p\)，设 \(f_i\) 表示以 \(p_i\) 结尾的 LIS 的长度。
考虑排列计数的套路令所有元素 \(+1\) 然后塞一个 \(1\) 进去或者直接塞一个 \(n\)。这里考虑后者更简单。
容易发现 \(f_i\) 等价最小表示法的状态数，于是我们就得到了一个比较优秀的算法，但是还是跑不过去。
考虑一个神奇的过程，加入一个 \(n\) 后，假设是加到了 \(i\) 上，那么有 \(f_i=\max_{j=1}^{i-1}f_j+1\)。
于是我们设 \(g_n=\max_{i=1}^{n}f_i\)，不再在状态上维护 \(f\) 而是 \(g\)。
容易发现相邻的 \(g\) 最多差 \(1\)，于是可以把这个状压下来。复杂度 \(O(n2^n)\)。
正解就是，用这个状压打表即可。。。。。。
标签：状态,P4484,一个,题解,max,神奇 From： https://www.cnblogs.com/lmpp/p/16723277.html