题解 [SCOI2009]粉刷匠
次阅读
2 min read
本来应该是个挺好想的 dp 的,然而自己做的时候居然没有想到拎出去处理,所以简单记录一下吧。
行,每行 个,可以涂 次颜色,求最大能匹配的颜色数。
显然有 dp 是前 行涂 次的方案。然后因为行和行之间相互独立,只需要知道当前这一行取每一个的方案就可以了。但是 的时间已经达到了一百多万,似乎里面怎么样都没有办法枚举状态了,何况还需要枚举当前一段的起点呢。
但这个问题其实非常好处理,因为每一行的这些状态都是和 无关的,所以直接设个 表示第 行到 个刷 次的最大匹配数,在那个 dp 外面做一遍就可以了。
为什么会想不到这个呢?可能是因为我一直想着节约空间,一行求出来之后可以直接弃掉状态,所以没有想到拉到外面去做,所以一时走不通的时候还得“回滚”一下,到更朴素的算法中去考虑优化。