状压dp2 2018年全国多校算法寒假训练营练习比赛(第二场)

https://www.nowcoder.com/acm/contest/74/F

上一篇状压dp例题由于每个位置都含有一个非负数,所以不需要判断能不能每个位置是否能取,

而这一道题由于地图已经说明每个位置是否能取,所以需要多加一步:将地图二进制化

状压dp2
2018年全国多校算法寒假训练营练习比赛(第二场)

然后把第一行的状态初始化存储在dp中

状压dp2
2018年全国多校算法寒假训练营练习比赛(第二场)

然后更新第二行之后的状态数组

状压dp2
2018年全国多校算法寒假训练营练习比赛(第二场)

最后找到最终状态数

状压dp2
2018年全国多校算法寒假训练营练习比赛(第二场)

主要注意

1、本题由于不是每个位置都能取,所以需要将地图需要二进制化

 2、dp的更新是dp[i][q] += dp[i-1][w];

  3、(state[i]&NUM[0])!=state[i];即&与!=必须要加括号!!!

状压dp2
2018年全国多校算法寒假训练营练习比赛(第二场)