题解 CF1051D 【Bicolorings】

2018-10-03 21:11:12


显然是DP了。考虑到黑白格,大概是个状压DP。

那么设 $f[i][j][k]$ 表示前i列,有j个联通块,第i列状态为k的方案数。

容易得到:

$$f[i][j][0]=f[i-1][j][0]+f[i-1][j][1]+f[i-1][j][2]+f[i-1][j-1][3]$$

$$f[i][j][1]=f[i-1][j-1][0]+f[i-1][j][1]+f[i-1][j-2][2]+f[i-1][j-1][3]$$

$$f[i][j][2]=f[i-1][j-1][0]+f[i-1][j-2][1]+f[i-1][j][2]+f[i-1][j-1][3]$$

$$f[i][j][3]+=f[i-1][j-1][0]+f[i-1][j][1]+f[i-1][j][2]+f[i-1][j][3]$$

然后大力DP即可。

注意边界为 $f[1][1][0]=f[1][2][1]=f[1][2][2]=f[1][1][3]=1$ 。

代码见蒟蒻的blog