状态压缩 LIS

LIS

LIS（最长上升子序列），nlogn的方法是维护一个数组，每次插入一个数字，插入到第一个大于等于这个数的位置上， 这样能保证后面的数尽可能多的插入数组中

状态压缩

如果已知LIS最长为10个， 那么我们就可一个用状态压缩的方法模拟nlogn的思路计算LIS，这样每个LIS的状态也能用一个数字保存下来

int update(int pos, int x) {// 在之前存在的数字中找到第一个大于等于的数， 删除for (int i = pos; i <= 9; ++i) {if (x & (1 << i)) {x ^= (1 << i);break;}}// 插入这个数return x | (1 << pos); }

总结

以上是生活随笔为你收集整理的状态压缩 LIS的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。