题解 UVA10559 【方块消除 Blocks】
BackSlashDelta · · 题解
❮UVA10559❯
➤ 闲言
奈何本人愚笨，愣是被这道题卡了近一天。看过了大佬们的题解之后还是不能太理解。最后还不得不结合了这里才终于算是理解了怎么做和为什么这么做。所以写篇题解加深印象，顺便帮助他人理解。
须知：缩进级以内的内容为辅助理解内容，不是必要的，理解了可以跳过。本题解讲的较为详细，需要耐心阅读。标题仅仅表示段落内的主要内容，为理解通透建议联系上下段或通读全文。标题前面的特殊符号没有任何其他意思，仅仅用于区分标题等级。本人
➤ 题面
给定一个序列，序列上的每个格子都有（且只有）一种颜色。连续的具有相同颜色的格子可以被消去，并获得消去的子区间长度的平方的贡献。且被消去的子区间两端的子区间会被连接。求最大贡献。多组数据。
➤ 题解
❖ 升维
首先不难发现：贪心的策略是错误的。因为我们可以先消除一些不符合贪心策略的区间来使得一些小区间合并成大区间并获取更多的贡献。因此，考虑区间 DP。
依照传统思维，我们使用 dp[begin][end] 来表示消去子区间 a[begin] 到 a[end] 的最大贡献。但是如果你有尝试推导，你就会发现——贡献不是简单相加或者相乘，而是乘方相加，且乘方随长度改变而改变。这大大提升了转移的难度。（至少我没做出来，我不知道有没有人可以二维转移）。因此我们考虑：加入维度。
❖ 方程
思考：如果我们找到了一段颜色相同且连续的区间，我们可以：（一）消去它，获得贡献，并连接它两边的区间（二）保留它，等待它两边的区间被消去以和其他相同颜色的区间合并成更大的区间。考虑第二种情况：我们保留当前区间（假定当前区间颜色唯一），并找到当前区间右边的、和当前区间颜色相同且不与当前区间连续的另一个区间（假定存在），我们消去这两个区间夹住的区间，合并两个目标区间并消除以获得贡献。
于是刚才这么大段话应该长这样：
那我们多开两维来记录下标吗？可以，但没必要。而且我们可能会和多个不连续的区间合并以得到更大的贡献。观察到贡献与位置无关，而且记录下标的目的就是为了计算长度，我们考虑：新增一维，用于记录我们在当前区间右侧保留的准备和当前区间一起消除的区间的长度。表示为：dp[begin][end][rExt]
考虑到区间内可能并不一定颜色唯一，我们以 a[end] 为“标准“。也就是说：我们用 dp[begin][end][rExt] 表示对于当前区间 a[begin] 至 a[end]，在该区间右侧（不包括 end）有数量为 rExt 的与 a[end] 颜色相同的格子会和 a[end] 一起消除。所以状态 dp[begin][end][rExt = 5] 长这样：
当然，上面的只是一个例子。在那个例子中，后面还有两个
4没有被状态包含（也就是我们不合并那两个4），所以还会肯定还有状态dp[begin][end][rExt = 7]，长这样：相应的，状态
dp[begin][end][rExt = 0]表示仅仅消除当前区间，不涉及后面的任何东西。长这样：
❖ 转移
还记得我们的两种选择吗？是的，保留或消除。于是我们猜想：也会有保留和消除的两种转移。
✜ 消除
依然是考虑到区间内可能并不一定颜色唯一，既然之前以 a[end] 为“标准”，不妨就消去 a[end]。但是想想就知道，单纯的消去 a[end] 这一个位置一定不会更优，那我们就消除一个区间。区间都是有个长度的，上面我们已经处理完了“标准”右侧的事情，那么看看左边。我们以 a[end] 向左蔓延，令 lExt 表示 a[end] 向左蔓延能找到的最“远”的、不超过左端点 begin 的点。
举几个例子：
我们有了标准点（a[end]）、标准点左端长度（lExt）和标准点右端长度（rExt），整个准备消除的区间的长度就可以计算了——贡献也能计算了。但是贡献的出现一定意味着状态的变化。消除完这个区间后，这个区间就不复存在了（rExt 只要有值，就意味着会消除夹在两目标区间中的所有值，这个在定义中已经讲明。关于这个的转移会在接下来的 ✜ 保留 中讲到），因此剩下的区间就是 a[begin] 到 a[lExt - 1]。那么转移就出来了：（Sqr(x) 表示 x 的平方，即 x * x）
dp[begin][end][rExt] <={ dp[begin][lExt - 1][0] + Sqr((end - lExt + 1) + rExt) }✜ 保留
相应的，我们也要考虑如果保留这段区间我们的贡献从何而来。既然保留这一段区间，我们肯定需要在当前区间内找到一个和“标准”同色的来进行转移，因为只有这样才有可能合并区间以使得答案更优。不然为什么不直接执行刚才消除的操作呢？反正留到最后也没有使它的贡献变大，留着干啥？同时为了保证答案更优，且转移次数更少，我们在找到了同色区间的最右端点时再转移。于是我们找到了保留的转移的限制条件。
If (a[brkp] == a[end] && a[brkp] != a[brkp + 1])既然是找到了一个同色的，那我们就以该点为断点（brkp），将序列分割为两部分：从 a[begin] 到 a[brkp]、从 a[brkp + 1] 到 a[lExt - 1]（因为我们已经确定 lExt 是和右边一起消去的，所以不必枚举到更右边的位置）。因为是保留，所以没有额外贡献，于是转移出来了：
/{ dp[begin, brkp, end - lExt + 1 + rExt] }
dp[begin][end][rExt] <={ + }
\{ dp[brkp + 1, lExt - 1, 0] }❖ 实现
为了方便，我使用了记忆化搜索的架构。
inline int DDFS(int begin, int end, int rExt) {
if (begin > end) { // 不合法区间，
return 0; // 返回一个不影响答案的 0
}
if (dp[begin][end][rExt]) { // 该区间已经有值了，
return dp[begin][end][rExt]; // 返回该值，不必再算
}
int lExt = end; // 游标准备，
while (begin <= lExt && a[lExt] == a[end]) { // 向左蔓延！
lExt--;
}
lExt++; // 回弹一格，因为肯定是不合法时才弹出的
dp[begin][end][rExt] = DDFS(begin, lExt - 1, 0) + Sqr(end - lExt + 1 + rExt); // “消除”转移
for (int brkp = begin; brkp < lExt; brkp++) { // 枚举断点
if (a[brkp] == a[end] && a[brkp] != a[brkp + 1]) { // “保留”的限制与转移
dp[begin][end][rExt] = std::max(dp[begin][end][rExt],
DDFS(begin, brkp, end - lExt + 1 + rExt)
+ DDFS(brkp + 1, lExt - 1, 0));
}
}
return dp[begin][end][rExt]; // 返回答案
}至于答案，应该不用我说。
状态
dp[1][n][0]表示对于区间1~n，右端不保留（你也没法保留）的最大贡献。