题解 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}$ 是个较优解。
但是这个「通常情况」指的是什么呢?
$a_{i-1} \times a_i + a_i \times a_{i+1} \le a_{i-1} \times a_{i} \times a_{i+1}$,即 $a_{i-1} + a_{i+1} \le a_{i-1} \times a_{i+1}$,然而后面这个等式必须要在 $a_{i-1},a_{i+1} > 1$ 的情况下才成立。
因此当某个 $a_{i} = 1$ 时,将会有更优解。
于是最终的贪心方法为:将序列从每个 $1$ 的位置分开成若干段,每一段内的代价为 $\sum a_{i} \times a_{i+1} + \min a_i$,最后再加上中间 $1$ 的个数即可。
```cpp
const int N = 1e6 + 7;
int n, a[N];
ll ans = -1;
int main() {
rd(n), rda(a, n);
for (int i = 0, j = 1; i <= n; i = j, j = i + 1) {
while (j <= n && a[j] != 1) ++j;
++ans;
if (i + 1 != j) ans += *min_element(a + i + 1, a + j);
for (int k = i + 1; k < j - 1; k++)
ans += a[k] * a[k+1];
}
print(ans);
return 0;
}
```