超级胶水（第十一届蓝桥杯）

题目

小明有 $n$颗石子，按顺序摆成一排。他准备用胶水将这些石子粘在一起。

每颗石子有自己的重量，如果将两颗石子粘在一起，将合并成一颗新的石子，重量是这两颗石子的重量之和。

为了保证石子粘贴牢固，粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比，本题不考虑物理单位，认为所需要的胶水在数值上等于两颗石子重量的乘积。

每次合并，小明只能合并位置相邻的两颗石子，并将合并出的新石子放在原来的位置。

现在，小明想用最少的胶水将所有石子粘在一起，请帮助小明计算最少需要多少胶水。

输入格式
输入的第一行包含一个整数 $n$，表示初始时的石子数量。

第二行包含 $n个整数w_1,w_2,\dots ,w_n$，依次表示每颗石子的重量。

输出格式
一个整数表示答案。

数据范围
$1\le n\le 10^5,$
$1\le w_i\le 1000$
输入样例1：

3
3 4 5

输出样例1：

47

输入样例2：

8
1 5 2 6 3 7 4 8

输出样例2：

546

代码(python版本)

n=int(input())
arr=list(map(int,input().split()))
res=0
cur=0
for i in range(len(arr)):
    res+=cur*arr[i]
    cur+=arr[i]
print(res)
1
2
3
4
5
6
7
8

代码（cpp版本）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;
const int N = 1e5+10;
int arr[N];
int main()
{
    cin>>n;
    for (int i = 0; i < n; i ++ )
    cin>>arr[i];
    
    LL res=0,cur=0;    
    for (int i = 0; i < n; i ++ )
    {
        
        res+=cur*arr[i];
        cur+=arr[i];
    }
    cout<<res<<endl;
    
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

思路

看到这题，首先看一下数据范围为1e5，思考一下，那么最大的时间复杂度为$O(nlogn)$,最多时间不能超过这个。现在心里有数了，就可以开始做题，首先拿到题目，首先暴力骗分 看一下常规思路。我们先模拟一下：
假设现在有三个石头，质量分别为$a_1,a_2，a_3$，那么：
第一次将最左边的两个石头合并，需要的胶水量就是$a_1\ast a_2$
现在只有两个石头了，质量分别为$a_1+a_2,a_3$
那么将这两个石头合并之后，需要的胶水量是$(a_1+a_2)\ast a_3$
一共需要的胶水量是$a_1\ast a_2+(a_1+a_2)\ast a_3$

假设现在有四个石头，质量分别为$a_1,a_2,a_3,a_4$，那么：
第一次将最左边的两个石头合并，需要的胶水量就是$a_1\ast a_2$
现在还有三个石头，质量分别为$a_1+a_2,a_3,a_4$
继续将左边的两个石头合并之后，需要的胶水量是$(a_1+a_2)\ast a_3$
现在只有两个石头，质量分别为$a_1+a_2+a_3,a_4$
将剩余的两个石头合并，需要的胶水量是$(a_1+a_2+a_3)\ast a_4$
一共需要的胶水量是$a_1\ast a_2+(a_1+a_2)\ast a_3+(a_1+a_2+a_3)\ast a_4$

到这里就找到了规律，就是胶水量为$a_1\ast a_2+(a_1+a_2)\ast a_3+(a_1+a_2+a_3)\ast a_4+(a_1+a_2+a_3+a_4)\ast a_5+......+(a_1+a_2+...+a_{n-1})\ast a_n$

然后代码中cur代表当前的重量，也就是上面的规律中的括号中的数。