洛谷 P6196 3月月赛 ERR1 代价

题目链接

Solution

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

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

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

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

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

并且可以证明，按照上面的规则，无论删除的顺序如何，删完 (n-1) 个数后答案总是相同的，即为：(a_1*a_2 + a_2*a_3 + ... + a_{n-1}*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] = a[n + 2] = 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;
 }