题目再现：
链接跳转：[蓝桥杯 2020 省 A1] 超级胶水 - 洛谷
# [蓝桥杯 2020 省 A1] 超级胶水
## 题目描述
小明有 $n$ 颗石子，按顺序摆成一排，他准备用胶水将这些石子粘在一起。
每颗石子有自己的重量，如果将两颗石子粘在一起，将合并成一颗新的石子，重量是这两颗石子的重量之和。
为了保证石子粘贴牢固，粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比，本题不考虑物理单位，认为所需要的胶水在数值上等于两颗石子重量的乘积。
每次合并，小明只能合并位置相邻的两颗石子，并将合并出的新石子放在原来的位置。
现在，小明想用最少的胶水将所有石子粘在一起，请帮助小明计算最少需要多少胶水。
## 输入格式
输入的第一行包含一个整数 $n$，表示初始时的石子数量。
第二行包含 $n$ 个整数 $w_1, w_2, \cdots, w_n$ 依次表示每颗石子的重量。
## 输出格式
输出一行包含一个整数，表示最少需要的胶水数。
## 样例 #1
### 样例输入 #1
```
3
3 4 5
```
### 样例输出 #1
```
47
```
## 样例 #2
### 样例输入 #2
```
8
1 5 2 6 3 7 4 8
```
### 样例输出 #2
```
546
```
## 提示
对于 $20\%$ 的评测用例，$1 \le n \le 15$。
对于 $60\%$ 的评测用例，$1\leq n \leq 100$。
对于 $80\%$ 的评测用例，$1\leq n \leq 1000$。
对于所有评测用例，$1\leq n \leq 10^5$，$1 \leq w_i \leq 1000$。
蓝桥杯 2020 第一轮省赛 A 组 I 题。
思路解读--前缀和：
拿到这道题第一眼看本来想着是计算每个数字之间的间距都需要多少胶水，然后从需要的最小的胶水数开始这么依次循环，不过这个思路乍一看这么普通，肯定卡时间复杂度或者难以实现，新手刚开始做题很容易陷入这样的自然思路，然后暴毙而亡。根据我多年的经验，解题思路一定在题干中，所以我重新读了一遍题干，然后举了3个数的例子，我惊奇的发现如果三个数是3 4 5的话，不管我先合并3和4还是先合并4和5，结果居然都是一样的，于是我开始了四个数的尝试，发现答案也是如此，于是我开始思考为什么是一样的（上面这个尝试恰恰是解决这道题的关键，如果没有尝试没有发现这个原理，那么这道题很难做出来，所以鼓励新手刚接触题目没有思路可以先尝试）。
其实想一想也可以理解为什么相等，加入我的石头是3 4 5，如果我先合并4和5，那么由于题目规定合并后质量是原来的加和（而不是乘积，这个前提条件决定了答案相等，不过是乘积反而与常识不符），也就是说合并后我们其实可以分开来看，将这个合并后的9看成4+5，那么如果我们要继续合并，就要3*（4+5），也就是说，我们相当于做了一次3*4和3*5，还是合并3和4以及合并3和5，这时候能意识到其实顺序并不重要，因为你5合并过来后还要跟3合并，如果先合并3和4也是一样的道理，你的3合并过来后还是要和5合并的，所以顺序无所谓，每个人都要和除了自己之外的所有石头进行一次胶水合并。
诶！？除自己之外的所有数？，这个思路让我想起来我前几天做的一道题也很类似，那道题用的是前缀和，所以在这道题也使用前缀和进行求解，那么就是当我输入一块石头后，我将他与他前面的所有石头和进行一次相乘，当输入完成后，我的结果也就完成了。比如我输入的5是第三个石头，那么我输入它之后，我让5去乘以前两个的石头后，是不是相当于和这2个石头进行胶水合并，然后后面输入的所有数都会和它们前面的石头和进行相乘，那么这个过程里，我的5也和后面输入的数进行和胶水合并，所以最后输入结束后就能得到答案了。
前缀和代码：
#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
int main()
{
ll n;
cin >> n;
vector<ll> stone(n);
vector<ll> sum(n);
cin >> stone[0];
ll res = 0;
sum[0] = stone[0];
for (ll i = 1; i < n; ++i)
{
cin >> stone[i];
sum[i] = sum[i - 1] + stone[i];
res += sum[i - 1] * stone[i];
}
cout << res;
return 0;
}最后注意就是long long别忘了就行
标签：A1,题解,石子,合并,蓝桥,leq,胶水,输入,样例 From： https://blog.csdn.net/qq_73848829/article/details/141728086