二进制操作积累

1. 不与左右相同(不含两个相邻的1) (x<<1&x)||(x>>1&x)
2. 不与左右两列相同(x<<1&x)||(x>>1&x)||(x<<2&x)||(x<<1&x)
3. 不与上一行同一位置相同 state[i]&state[j]==0 (i>j)
4. 不与上两行同一位置相同 state[i]&state[j]==0 && state[i]&state[k]==0 (i>j,j>k)
5. 不与左上右上相同 x=state[i]|state[j] (x<<1&x)||(x>>1&x)

棋盘式DP

• 预处理操作

  1.预处理出每个行可以存在的合法方案 vector<int> state(有时要根据题目预处理对应状态的一些属性)
  2.从每个行可以存在的合法方案中,计算出这些方案可能转移过来的状态 vector<int> head[N];

• 动态规划

for 行数
    for 所有限制条件
        for 第i行可能存在的状态(state.size())
            if(满足限制条件)
                依据属性更新f数组

• 可能存在的限制条件

  1. 行间的相互关系
     check(a)——>横向限制条件
     a&b==0 保证不同行同列间不存在矛盾——>十字形限制条件
     check(a|b)==0保证斜线不存在1——>井字形限制条件
     1064. 小国王
  2. 地图限制.
     地图限制采用对每行状态转化成一个整数,障碍处为1,与该行方案进行&操作,若不为0则说明矛盾(地图不合法位置为1)
     327. 玉米田

具有地图限制的问题,一般不会预处理出head[N],因为每行可行状态组都不一样,处理起来很麻烦,所以应该直接遍历state,判断state[i]是否满足地图限制和行间关系

遍历状态是通过的vector下标,f的第二维度s存储的也是下标而不是具体的state

集合式DP