自己给公司做网站该怎么做,网站开发晋升空间 路径,跨境电商信息服务平台有哪些,个人网站网站建设状压DP 介绍介绍例题 总结 介绍
介绍
状态压缩就是使用某种方法#xff0c;简明扼要地以最小代价来表示某种状态#xff0c;通常是用一串01数字#xff08;二进制数#xff09;来表示各个点的状态。这就要求使用状态压缩的对象的点的状态必须只有两种#xff0c;0 或 1简明扼要地以最小代价来表示某种状态通常是用一串01数字二进制数来表示各个点的状态。这就要求使用状态压缩的对象的点的状态必须只有两种0 或 1当然如果有三种状态用三进制来表示也未尝不可。 状态压缩DP顾名思义就是用状态压缩实现DP。 不过呢对于装压DP来说不一定是二进制。
状压DP主要分为集合式和棋盘式本文只讨论棋盘式。 集合式点这里。
例题
点这里。
总结
对于棋盘式的状压DP有几种思考方式。
每行每行考虑逆推DP。每列每列考虑逆推DP。每个格子每个格子考虑顺推DP。每个格子每个格子考虑dfs顺推。同时考虑两行三维DP适用于类似炮兵阵地的题目。考虑三进制状态压缩如炮兵阵地的解法 2 2 2。对于三维DP有可能炸空间可以考虑滚动掉一维。 记住
再三检查空间复杂度。检查时间复杂度。检查输入时的下标和枚举时的下标是否匹配。检查各种位运算的优先级是否有冲突该加的括号一定要加。检查状态的定义和输出。检查for的枚举顺序。
