首页 > 代码库 > 棋盘模型的状态压缩
棋盘模型的状态压缩
此类状压,往往是在棋盘上放置互相影响的棋子(限制或不限制个数),求方案数
如:
- 在棋盘上放K个行不相邻的棋子
- 在棋盘上放K个列不相邻的棋子(其实完全一样)
- 在棋盘上放K个行列不相邻的棋子
- 在棋盘上的合法位置放K个行列不相邻的棋子
- ......
诸如此类
该模型的特点:
- 对每一个位置只有两种状态
- 每一个位置的状态只受相邻的有限个状态影响
- 宏观看每行的可能状态具有相似性
以“在棋盘上放K个行列不相邻的棋子”为例
可以用01表示每个位置的状态,但这样转移其来极其麻烦——对于(i,j)他需要从(i,j-1)中(i-1,j)满足条件的状态转移,且为了往下转移,还要从(i,j-1)调出(i-1,j+1)来,这意味着对于(i,j-1),他之前的所有决策都得记下!!
故抛弃该思路,考虑行间整体转移
考虑行的相似性——他们都是01串,我们发现对行的可能状态是可以整体枚举的,即枚举合法的01串,且枚举结果对每一行都适用。枚举时可以满足左右不冲突,于是现在只需要满足上下不冲突就好了。而这个是可以整行操作的——位运算&:当a&b==0时,行a转移至行b合法。
于是f[i][j][l+c[j]]=Σf[i-1][k][l](i:行数;j:本决策中本行的状态编号,即本决策中本行的状态的01串,他的十进制值为s[j];l+c[j]:此时共放入几个棋子)
这就是状态压缩了。
要点:
- 对每行的可能情况构造合法的01串,可以但不限于预处理
- 同过位运算判断出行间的关系,整体转移。
相关习题:
玉米田Corn Fields
互不侵犯King
炮兵阵地
中国象棋(这题的正解好像跟今天讲的没关系,不管啦)
棋盘模型的状态压缩
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。