洛谷月赛 ERR1 代价

题目链接

Solution

假设存在一个数列，(a_1, space a_2, space a_3, space a_4, space a_5)

考虑删除 (a_4, space a_5) 的顺序：

若先删除 (a_4)，代价为 (a_3 imes a_4 imes a_5 + a_3 imes a_5)

若先删除 (a_5)，代价为 (a_4 imes a_5 + a_3 imes a_4)

第一种显然不比第二种优，所以得出结论：每次都删除两边的数（这里的两边是指与 (1) 相邻的数）。

并且可以证明，按照上面的规则，无论删除的顺序如何，删完 (n-1) 个数后答案总是相同的，即为：(a_1 imes a_2 + a_2 imes a_3 + ... + a_{n-1} imes a_n)

若现在还剩最后一个数字，它的值会直接加到答案中。我们肯定希望这个数字越小越好，所以直接在数列中找到一个最小值作为最后删除的数。

需要注意的是，数列中若出现 (1)，可以看作是把序列切割成了几段，每一段要分别处理。这些 (1) 最终也要删除并计入答案。

Code

#include <iostream>
#include <cstdio>
using namespace std;
const long long INF = 0x3f3f3f3f;
long long n, ans = 0, a[2000000], min_ = INF;
int main()
{
    scanf("%lld", &n);
    a[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        if(a[i] == 1)
        {
            if(min_ != INF) ans += min_;
            ans++, min_ = INF;
            continue;
        }
        if(a[i - 1] != 1) ans += a[i] * a[i - 1];
        min_ = min(min_, a[i]);
    }
    if(min_ == INF) min_ = 0;
    printf("%lld", ans + min_);
    return 0;
}