AGC035D Add and Remove

题意：初始时有长度为 的序列 ，多次进行如下操作，知道只剩两个元素 :

• 选择 。
• 令 加上 ，然后将 从序列中删除。

最小化最后剩下的两个元素的和。

，时限 。

---

操作只会影响相邻的元素，联想到区间 DP。

若正着考虑，一次操作后，两侧还能互相影响。

不妨倒着考虑。先考虑最后一次操作，此时有 ，删除了 。

那么 会加一次到 ，加一次到 ，贡献系数为 。

考虑之前的情况，形如 ，其中 中的元素，有些贡献到了 ，有些贡献到了 。 中的元素有些贡献到了 ，有些贡献到了 。

这里，两种贡献的系数是不同的， 的贡献系数是 ，而 是 。

于是，可以设计如下 ：

设 表示删除区间 内的元素，向 的贡献的系数为 ，向 的贡献的系数为 ，贡献的最小值。

答案即为 。

有如下转移：

直接进行不记忆化的搜索，复杂度递推式如下：

有上界 。