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

题目

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

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

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

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

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

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

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

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

数据范围
$1≤n≤10^5,$
$1≤w_i≤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=0cur=0for i in range(len(arr)):res+=cur*arr[i]cur+=arr[i]print(res)

代码（cpp版本）

#include #include #include 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;}

思路

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

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

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

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

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

题目

代码(python版本)

代码（cpp版本）

思路

最新关注

热文推荐

Java实现从Redis中批量读取数据

C语言——数据的输入输出

【C语言】通讯录实现（下）

【ROS入门】机器人系统仿真——相关组件以及URDF集成Rviz

直播程序源码技术分享主播邀请上麦功能

TransactionTemplate编程式事务

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

题目

代码(python版本)

代码（cpp版本）

思路

相关文章

最新关注

热文推荐