2020-2021:teams:manespace:状压dp
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:manespace:状压dp [2020/07/16 16:24] iuiou 创建 |
2020-2021:teams:manespace:状压dp [2020/07/16 16:27] (当前版本) iuiou |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| **状压的描述**：所谓状压，其实就是状态压缩，就是把一些多维的状态用一个简洁的二进制数来表示。比如这样一个问题[[https://www.luogu.com.cn/problem/P4011]] | **状压的描述**：所谓状压，其实就是状态压缩，就是把一些多维的状态用一个简洁的二进制数来表示。比如这样一个问题[[https://www.luogu.com.cn/problem/P4011]] | ||
| - | 题目中明确指出，m把钥匙，没把钥匙可以开一个对应的门，在迷宫中行走的时候，自己身上拥有钥匙的数量和种类肯定会变化，这给不管是dp还是bfs都带来了麻烦，所以考虑，设置一个m位2进制字符串，第i位是否为1表示当前是否有第i把钥匙，这样在bfs过程中可以通过位运算来改变当前的状态。这样就处理起来方便很多。 | + | 题目中明确指出，$m$把钥匙，没把钥匙可以开一个对应的门，在迷宫中行走的时候，自己身上拥有钥匙的数量和种类肯定会变化，这给不管是$dp$还是$bfs$都带来了麻烦，所以考虑，设置一个$m$位2进制字符串，第$i$位是否为1表示当前是否有第i把钥匙，这样在$bfs$过程中可以通过位运算来改变当前的状态。这样就处理起来方便很多。 |
| 上题代码 | 上题代码 | ||
| 行 64: | 行 64: | ||
| </hidden> | </hidden> | ||
| - | 而dp就是状态的转移，状压dp就是将状态做01压缩后成为dp数组的一维，然后做转移而已。具体怎么设定数组和怎么转移还要具体问题具体分析。 | + | ======总结====== |
| + | 而dp就是状态的转移，状压dp就是将一系列因素的状态做01压缩后成为dp数组的一维，然后利用位运算的知识做转移而已。当然，前提是条件的每个因素的状态是二元的，是或者不，可以用0和1来表示，不然还是不可以用状态压缩的。具体怎么设定数组和怎么转移还要具体问题具体分析。 | ||
2020-2021/teams/manespace/状压dp.1594887890.txt.gz · 最后更改: 2020/07/16 16:24 由 iuiou
