题解 AT5141 【[AGC035D] Add and Remove】

· · 题解

可以发现 A_1 和 A_N 没啥用，不用考虑它们，然后最后加到答案里去就行。

那也就是说，现在有 N - 2 个数排成一行，你每次可以删掉其中一个，它就会加到左右两边去。

特别的，如果它在最左边，它就会被加到一个变量 L 上，如果它在最右边，它就会被加到一个变量 R 上。

最后要让 L + R 最小。

这时可以考虑倒着做。假设最后一个删掉的元素，是 i。

那么 i 左边的数，一部分扔到 L 里了，一部分扔到 i 上了，i 右边的数，一部分扔到 R 里了，一部分扔到 i 上了。

然后删除 i 本身，就有那些扔到 i 上的数，以及 i 本身，都会被加到 L 和 R 上。

那么我们假设，i 左边的数删除后，加到 i 上，总共加了 x。那么这 x 最后产生的贡献就是 2x，因为加到了 L 和 R 上。

右边同理，只不过换了个方向，也是两倍贡献。

既然倒着考虑了，那就要想到区间 DP。我们观察 i 左边的区间，这段区间中的数，加到左边会对总答案贡献 1 倍，但是加到右边会贡献 2 倍。

于是定义如下状态：dp(l, r, cl, cr) 表示考虑区间 [l, r] 中的数，把它们删除后，会对总答案贡献 cl \cdot L + cr \cdot R，要使这个贡献最小。

则最终答案为 dp(2, N - 1, 1, 1) + A_1 + A_N。

有转移：

dp(l, r, cl, cr) = \min_{i = l}^{r} [ dp(l, i-1, cl, cl + cr) + dp(i + 1, r, cl + cr, cr) + (cl + cr) A_i ]

特别地，如果 l > r，则 DP 值为 0。

容易发现，DP 状态数的上界是 \mathcal O (N^2 2^N)，因为区间只有 \mathcal O (N^2) 对，而后面的系数的增长可以看作一个 N 层的二叉树的形态。

经过一些精细计算，其实 DP 状态数和转移数只有 \mathcal O (2^N)，这里就略去不证了。