P1389-序列游戏 题解

qjyzLfy · 2020-03-05 00:42:38 · 题解

前言

1. 作者很菜，于是他假定部分读者和他一样菜，因此写得既详尽又冗长。

2. 若无特殊强调，本题解中的“连续”一般是指位置上而非数值上的连续。

3. 输入格式中的 V_i 和 A_i 在文中分别记为 val_i 和 num_i 。

4. 本题解设置了多层标题，建议读者跳过已理解的部分。

分析

题意：有一个正整数数列，每次消去连续的一段合法的数字，得到这段数字长度对应的分数。数列不必全部消去，求最终得分的最大值。其中“合法”，是指数字可分为恰有一个数重合的前后两段（每一段长度可为 1 ），前一段以 1 为公差递增，后一段以 -1 为公差递减。

这样的题目应该是用区间动规。

由于消去一些数字必须先使之连续，也就是必须先消去这段数字中间的所有数字，计算部分消去某段区间的最大得分就不太可行，因为转移时难以判断两个数字在什么条件下连续。所以更可行的办法计算完全消去一段连续区间的最大得分，记为 ans_{l,r} 。

最后为了得出部分消去整段数列的最大得分，可对数列进行划分，直到每一段区间要么全部都被消去，要么全部都未被消去为止。这显然是可行的。

动规转移

消去某段区间时，只有两种可能：一次性消去，或分步消去。

若分步，则必有最后一步。这是绝大多数动规的突破口。

最后一步是消去“连续”的一段数字，而这段数字初始时不一定连续，所以其空缺处的数字都已经被消去了。当然，这些空缺都构成连续区间，而且彼此独立。

所以可以枚举最后一步消去的数字，然后计算被这些数字隔离出的所有连续区间的 ans 值之和，再加上消去数字的得分。其最大值就是当前计算的区间的 ans 值。

计算答案

现在要由完全消去某区间的得分的最大值，得出部分消去某区间的得分的最大值。可以用一个简单的动规。

一段区间，在最优方案下，除非它被完全消去，否则就可以被找到一个未消去的点 （废话）。从这个点处（左边或右边）把区间分成两段，两段各自按最优解处理，就可以得到当前处理区间的最优解。所以只要枚举“断点”，就可以由小区间最优解得到大区间最优解了。

实现

在完全消去时（第一次动规）：

无疑，转移时枚举消去的数字要靠搜索。为避免一个点一个点地找数值上相邻的数字（那样又难写又慢），可以使用（假）指针标记相邻数字。

这是就会发现可消情况可以表示为两棵树。把数列中的数视为点，为了使能一同消去的点连通，只需使让一棵树中每个点连接数值比它大 1 的点，让另一棵树中每个点连接数值比它小 1 的点即可。当然，这两棵树应该是单向的（从左到右或从右到左）。

现在我们有两种选择。

1. 最高点作根。向左向右分别建一棵下降的树。使用时分别在两棵树上搜索。

2. 最右边的点作根。向左建一颗向上的（即上升的，下同）树和一颗向下的树。使用时先在向上的树上搜索，并在每个子节点处尝试转换到向下的树上继续搜索。（当然从左边来也行）

显然方案 1 搜索的深度更小，因此似乎应该更快。但考虑具体操作就会发现，搜索时无法立即确定消去的数字的长度，因为左右两边相互独立。因此，也就无法确定最优解。所以选择方案 2 。

• 建树

数据范围很小，不妨枚举。第一个比当前点数值大 1 （小 1 ）的点为向上（向下）的树中当前点的长子，第一个与当前点数值相同的点为当前点的兄弟（两棵树中兄弟的情况是一样的，可以共用）。

• 动规的转移

假设待处理区间为 [l,r] ，简记为 S ， ans_{l,r} 表示处理相应区间的最大得分。

在 S 内枚举根节点 t 开始搜索，每搜索到一个点，判断当前得分（即最后一步要消去的数到此为止，后面的数不再被消去时的得分，下同）是否大于当前区间的得分。然后，如果是在向上的树上，就搜索其向上和向下的子节点，搜到向下的子节点时进入向下的树；如果是在向下的树上，就只搜索向下的子节点。直到子节点在 l 左边为止。（子节点不存在时将搜到 0 ，而 0<l 。）

其中，当前得分的计算方法是：用一个参数 red 记录消去数列中间空缺区间的得分。从父节点 f 进入子节点 s 时， red_{s}=red_{f}+ans_{s+1,f-1} 。再用一个参数 len 记录搜索到当前节点时消去数字的长度，最后 p 点的当前得分就是 red_{p}+ans_{l,p-1}+val_{len} 。显然要把根节点 t 处的 red 初始化为 ans_{t+1,r} 。

为方便处理中间的区间为空（即消去的数字原本就连续，或者消去的数字和端点 l,r 连续）的情况，令 ans_{i+1,i}=0 。

在部分消去时（第二次动规）：

这一步并不是复杂度的主要来源，可以无脑一些。下面用 ans'_{l,r} 表示部分消去区间 [l,r] 的最大得分。（读下一句话时请注意每个 ans 右上角有没有 ' 。）

先把单个点的最大得分 ans' 初始化，即 ans'_{i,i}=max\{ans_{i,i},0\} ，然后计算 ans'_{l,r} 时枚举断点 t ，令 ans'_{l,r}=max\{ans_{l,r},ans'_{l,t}+ans'_{t+1,r}\} 即可。

因为 ans' 是在 ans 的基础上与多个数比较取最大值得来的，可以直接用新最大值覆盖在原来的 ans 上，不用定义新变量还省了初始化。

优化

优化当然是针对复杂度最大的第一次动规进行的，特别是针对其中的搜索进行的。

优化 1 ：剪枝

搜索到一个点时，如果可以确定，不管接下来的情况再怎么顺利，都不能得到更优解，就可以剪枝了。

而最理想的情况应该是接下来所有点都连续的情况。因为这时可以绝对自由地选择消去方法。所谓“自由”是因为决定得分的只是每次消去的区间的长度，而所有长度“分配”方式现在都可以做到。

但即使如此依然有很多选择，而现在需要直接找到最优的一种。

按照游戏的正常逻辑，直接把一个长为 k 的合法区间消去，应该比把它拆分为两个短的区间再消去要优。否则，所有长为 k 的合法区间都可以这样拆分，就永远不会有消去长为 k 的区间的操作了。

但是出题人未必如此出题。不过，既然所有长度为 k 的区间都可以这样拆分，就用拆分后的得分代替原得分好了。即 val'_{k}=max\{val_{k},val'_{t}+val'_{k-t}\} 。这一步要对所有的 k 由小到大处理一遍。

这样做相当于把所有消去区间连续的消去操作“合并”了，所以不影响正确性。

在此基础上，消去一段连续合法数字的最优方法一定是直接一步消去，最理想情况下的最大得分也就是直接一步消去的得分了。

具体来说，对于区间 [l,r] ，搜索到 t 点时。假如 ans_{l,r} \ge red_{t}+val_{len+t-l} ，就可以剪枝了。

现在，可以搜到一个点时剪枝（就是上面的写法），也可以在将要搜索某个点之前就判断并剪枝。后面一种策略避免了进入下一级函数，因而更快。相应判别式略。

优化 2 ：省略

还记得搜索前需要枚举起点 t 。而如果最后一次消去的区间右端点为 t ，那么 t 右边的连续段（不含 t ）和左边的连续段（含 t ）必然是各自独立地消去的。因为其它消去操作不可能跨过 t 而消去其两边的数字。这时就可以直接用两段相加来代替搜索。即 ans_{l,r}=max\{ans_{l,t}+ans_{t+1,r},ans_{t=r}\} 。