状态压缩dp-蒲公英云

状态压缩dp

傷城~ 2022-09-12 05:56 149阅读 0赞

状态压缩dp与状态机模型很相似，都需要通过进一步划分状态使得状态定义更加清楚，状态机模型按照时序来划分集合，状态压缩dp使用二进制数字来划分集合，状态压缩dp一般都需要先预处理（先处理合法的状态，然后再处理合法的哪些状态可以相互转移），也即先记录下合法的状态，这样可以避免计算不合法的状态时间复杂度很高的问题，状态压缩dp大部分的代码都是类似的，一般分为两种类型：棋盘式和集合式，棋盘式相对比较简单一点，当我们看到题目中存在棋盘的时候分析是否可以使用状态压缩dp解决：

watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_17_color_FFFFFF_t_70_g_se_x_16

棋盘式状态压缩dp一般考虑一行一行地填或者一列一列地填，一行的每一个位置使用0和1来表示对应的状态，对应的状态定义和状态计算都是比较容易分析的，状态定义一般是根据题目要求的问题以及相关的限制进行定义的，状态计算对应的集合的划分，一般是找最后一个不同点，比较常见的是枚举所有上一个可以转移到当前状态的合法状态。一般在状态计算之前需要先预处理，常见的有两个预处理的过程：第一个预处理需要根据某个条件去除掉不合法的状态，常见的有当前这一行不能够有连续的两个1…，第二个预处理一般需要根据第一个预处理记录的合法状态来记录当前状态可以由哪些合法状态转移过来，其实描述的就是当前相邻两行或者相邻两列之间的关系，通过预处理之后我们在状态计算的时候就可以枚举在当前状态下可以由哪些合法状态转移过来，将当前这些合法状态的方案数目直接累加上到当前的状态上即可，通过两步的预处理之后一般会去除掉很多不合法的状态所以实际上合法的状态还是比较少的，这样可以大大减小后面枚举状态的时间复杂度。可以参考一下291蒙德里安的梦想和1064题小国王预处理的过程。在状态计算的时候一般是枚举当前这一行的状态和转移到当前状态的上一行的所有合法状态。