棋盘模型的状态压缩

    此类状压,往往是在棋盘上放置互相影响的棋子(限制或不限制个数),求方案数

    如:

  1. 在棋盘上放K个行不相邻的棋子
  2. 在棋盘上放K个列不相邻的棋子(其实完全一样)
  3. 在棋盘上放K个行列不相邻的棋子
  4. 在棋盘上的合法位置放K个行列不相邻的棋子
  5. ......

    诸如此类

    该模型的特点:

  • 对每一个位置只有两种状态
  • 每一个位置的状态只受相邻的有限个状态影响
  • 宏观看每行的可能状态具有相似性

    以“在棋盘上放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

炮兵阵地

中国象棋(这题的正解好像跟今天讲的没关系,不管啦)

Just close your eyes, you`ll be alright, no one can hurt you after you die.
原文地址:https://www.cnblogs.com/nietzsche-oier/p/6160390.html