传送门
官方题解做法。
注：因为黑格子上只能放黑棋，白格子上只能放白棋，所以有的时候没必要区分是格子还是棋
Step 1 - 找性质
- 对于一个极大棋子联通块，我们可以在它左边或者右边放一个棋子（具体来讲选择对应位置格子颜色的棋子然后放上一个相同颜色的棋子）
这意味着，我们对于我们可能的一个方案，我们只需要在可能的方案中的每个联通块中生成一个小段（我们称之为标记）然后就可以用这个小段来“长”出目标方案。
- 我们如果要新放一个标记，那必须满足当前所有与已放棋子相邻的格子（称作缺口）一定得是同一个颜色的（这样才能选择另一个颜色来做标记）
于是我们可以分类，将一个所有相邻格子都是白的情况下放的标记，称作白放置，否则称作黑放置。
-
在一个可能的最优方案中，只可能出现一种颜色的放置，即不会黑白放置都出现。
证明：不妨设先进行了一次白放置，后进行了一次黑放置。对于第二次黑放置，它要求所有段的缺口都是黑的，而第一次白放置要求所有段的缺口都是白的。所以在两次放置之间必须把所有白缺口的段都长成黑缺口。但段的生长本身不依赖其他段，所以你大可以在第一次就把所有白缺口长成黑缺口，然后把第一次变成白放置。
于是我们可以直接枚举答案是黑放置还是白放置，然后对两种情况取 min 即可。
不妨设答案是白放置。
- 白放置一定只能放黑棋子。然后我们又要求所有缺口都是白的，因此大部分情况下标记都是一个极大的黑联通块。
但第一次和最后一次的约束不太一样，具体的：
-
第一次因为是随便放，因此可以放一个白的单点，满足两边的缺口都是白的就行。
-
最后一次因为不用后面的生长，因此可以只放一个黑的单点。
Step 2 - DP
OK，我们已经找到了方案的组成部分，具体的有三种：
- 左右都是白的白点，称作 a1。
- 极大黑联通块，称作 a2。
- 黑点，称作 a3。
我们要求方案中的每个联通块都包含一个 a1,a2 或 a3。且 a1 和 a3 只能出现一次。
设计状态：f[i][0/1][0/1][0/1][0/1][0/1/2][0/1]。
表示：当前位置，用了 a1 吗？用了 a3 吗？当前格子选了吗？当前的联通块里有 a1 吗？当前的联通块里没开始 a2(0)，当前联通块里开始了但没结束 a2(1)，当前联通块结束了 a2(2)。当前联通块里有 a3 吗？
这是一个高达 96 种状态的 DP，不可能去手动转移。我们考虑给转移归类。
我们可以拆成两步：第一步先处理当前的这个点的状态，要不要放进 a1/a2/a3？第二步再直接转移到下一个点。
详细的可以看代码，写了注释。
Link