题解 P6196 【[EER1]代价】

xht · 2020-03-11 13:42:23 · 题解

考虑一种简单的删除方法，按照 1 \sim n 的顺序依次删除，这时的代价为 \sum_{i = 1}^{n - 1} a_{i} \times a_{i+1} + a_{n}。

实际上这已经是一个较优解了，事实上对于 i \in [1,n)，a_i, a_{i+1} 在最终的答案中一定都要被相乘一次。原因在于假设不被相乘，就意味着 a_i, a_{i+1} 其中有一个先被删除了，然而先被删除的时候一定有相乘过，因此矛盾。

现在我们找到了一个较优解 \sum_{i = 1}^{n - 1} a_{i} \times a_{i+1} + a_{n}，考虑如果变成最优解。

首先来看这个 a_n，显然可以变成 \min_{i=1}^n a_i，具体方法是，假设最小的位置为 p，我们先按照 1 \sim p - 1 的顺序依次删除，再按照 n \sim p + 1 的顺序依次删除即可。

再来看这个 \sum_{i=1}^{n-1} a_i \times a_{i+1}。

刚才提到每两个相邻的数一定要被相乘一次，但是相乘有两种情况。

上面的做法是从左往右依次删除，贡献为 a_{i-1} \times a_i + a_i \times a_{i+1}。

而如果从中间删除，贡献为 a_{i-1} \times a_{i} \times a_{i+1}。

通常情况下，前者要比后者小（因为前者只有两项相乘，而后者有三项），这也是为什么 \sum_{i=1}^{n-1} a_i \times a_{i+1} 是个较优解。

但是这个「通常情况」指的是什么呢？