相邻行列相互影响的状态类问题(类似状压dp的搜索)(POJ3279)

POJ3279http://poj.org/problem?id=3279

题意:黑白的板,每次选择一个十字形翻转(十字板内黑白互换,若是边界则不管),求最小将原图变为全白的策略。

这是一道对于每个格子的选择会对相邻格子造成影响的问题,回顾一下,这个问题和状压dp解决的问题的条件基本一致,而状压dp是求总方案数,这个是求最佳方案

操作上:状压dp,通过对第一行的状态进行枚举,然后对后面的每一行进行相应枚举,记录方案数,类似的,这道题,通过对第一行的状态进行枚举,然后对后面的每一行进行的操作是---查看之前行的格子是否还存在空缺,如果空缺就对当前行的格子进行操作(实际上和状压Dp的放木板问题类似)

原文地址:https://www.cnblogs.com/MekakuCityActor/p/8560046.html