CF392E Deleting Substrings

SmallR 喜欢一个叫做“删除子串”的游戏。在这个游戏中，你会得到一个整数序列 $w$，你可以对序列进行修改并获得分数。你唯一可以进行的操作就是（没想到吧？）删除子串。更准确地说，你可以选择若干个连续的 $w$ 元素，并将它们从序列中删除。我们把这些被选择的元素表示为 $w_{l},w_{l+1},...,w_{r}$。它们必须满足以下条件： - 对于所有的 $i$ 满足 $l \leq i < r$，都有 $|w_{i} - w_{i+1}| = 1$； - 对于所有的 $i$ 满足 $l < i < r$，都有 $2w_{i} - w_{i+1} - w_{i-1} \geq 0$。 删除选定的子串后，你可以获得 $v_{r-l+1}$ 分。只要还有合适的子串存在，你可以不断进行上述操作。你也可以在任何时候选择结束游戏。你的任务是计算在这个游戏中你能够获得的最大总分数。

第一行包含一个整数 $n$（$1 \leq n \leq 400$），表示 $w$ 的初始长度。 第二行包含 $n$ 个整数 $v_1,v_2,...,v_n$（$0 \leq |v_i| \leq 2000$），表示每种操作对应的得分。 第三行包含 $n$ 个整数 $w_1,w_2,...,w_n$（$1 \leq w_i \leq 10^9$），表示初始序列 $w$。

输出一个整数，表示你能得到的最大总分数。

由 ChatGPT 5 翻译