POJ 1390 Blocks DP

最开始以为这道题是简单的区间DP。我的想法是每次尝试删两边相同的,或者把区间一分为2。但是这个想法存在,问题,一旦一段序列,两段一个色。中间还有一段跟两段一个色,那么久可能存在一种最优解,是删掉3处颜色相同的间隔部分,然后统一删除掉这3个。当然也存在中间有多个和两段相同的情况。所以这么做是不对的。

后来查了题解,发现这个dp的构思方法很是巧妙。

为了方便转移和思考,我么先将相邻的同色块缩块。

dp[l][r][ex]表示消掉[l,r]这一区间,的最小代价。(ex表示右侧与r同色的色块的总长度)

边界显然是 sqr(ex+len[r]) (l == r)

我们考虑一下转移。

对于一个色块,我们显然有两种处理方法,一种是把r和ex那一部分直接消掉,考虑左面的剩余部分。

另外一种办法是考虑我r和左侧的某一块后最后一起消掉。我们枚举一下是哪一块。显然在递归的过程中,他会自己处理好,这两块中间颜色相同的部分怎么处理最优。那么转移如下。

最后记忆化搜索一下就好了。

发表评论