P8709 [蓝桥杯 2020 省 A1] 超级胶水

本文主要是介绍P8709 [蓝桥杯 2020 省 A1] 超级胶水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题描述

P8709 [蓝桥杯 2020 省 A1] 超级胶水

二、问题简析

看完题目，肯定会想到贪心，但是这题不需要贪心也能解决。

假设有 $4$ 颗石子：$a,b,c,d$。我们随意组合，得到结果：

$$\begin{array}{rl}ans& =bc+a(b+c)+(a+b+c)d\\ & =a(b+c+d)+b(c+d)+cd\end{array}$$

如果尝试其它的方式，得到的结果也是一样的。我们可以推测，$n$ 颗石子的结果为

$$ans=\sum _{i=0}^{n-2}(a_i\ast \sum _{j=i+1}^{n-1}{a}_j)$$

我们可以采用前缀和来优化 ${\sum }_{j=i+1}^{n-1}{a}_j$。

---

三、AC代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;int quickin(void)
{int ret = 0;bool flag = false;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')    flag = true;ch = getchar();}while (ch >= '0' && ch <= '9' && ch != EOF){ret = ret * 10 + ch - '0';ch = getchar();}if (flag)    ret = -ret;return ret;
}const int MAX = 1e5 + 3;
ll A[MAX], n, B[MAX];int main()
{#ifdef LOCALfreopen("test.in", "r", stdin);#endifn = quickin();ll tmp = 0;for (int i = 0; i < n; i++){A[i] = quickin();tmp += A[i];B[i] = tmp;}ll ans = 0;for (int i = 0; i < n - 1; i++){ans += A[i] * (B[n - 1] - B[i]);}cout << ans << endl;return 0;
}

---

完

这篇关于P8709 [蓝桥杯 2020 省 A1] 超级胶水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---