题解 [SCOI2009]粉刷匠

本来应该是个挺好想的 dp 的,然而自己做的时候居然没有想到拎出去处理,所以简单记录一下吧。

nn 行,每行 mm 个,可以涂 kk 次颜色,求最大能匹配的颜色数。

显然有 dp f[i][j]f[i][j] 是前 ii 行涂 jj 次的方案。然后因为行和行之间相互独立,只需要知道当前这一行取每一个的方案就可以了。但是 nknk 的时间已经达到了一百多万,似乎里面怎么样都没有办法枚举状态了,何况还需要枚举当前一段的起点呢。

但这个问题其实非常好处理,因为每一行的这些状态都是和 i,ji,j 无关的,所以直接设个 g[i][j][k]g[i][j][k] 表示第 ii 行到 jj 个刷 kk 次的最大匹配数,在那个 dp 外面做一遍就可以了。

为什么会想不到这个呢?可能是因为我一直想着节约空间,一行求出来之后可以直接弃掉状态,所以没有想到拉到外面去做,所以一时走不通的时候还得“回滚”一下,到更朴素的算法中去考虑优化。