iis网站配置 无法浏览,WordPress谷歌广告插件,北京网页设计公司就找兴田德润,江门模板建站源码题目
小明有 n n n颗石子#xff0c;按顺序摆成一排。他准备用胶水将这些石子粘在一起。
每颗石子有自己的重量#xff0c;如果将两颗石子粘在一起#xff0c;将合并成一颗新的石子#xff0c;重量是这两颗石子的重量之和。
为了保证石子粘贴牢固#xff0c;粘贴两颗石…题目
小明有 n n n颗石子按顺序摆成一排。他准备用胶水将这些石子粘在一起。
每颗石子有自己的重量如果将两颗石子粘在一起将合并成一颗新的石子重量是这两颗石子的重量之和。
为了保证石子粘贴牢固粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比本题不考虑物理单位认为所需要的胶水在数值上等于两颗石子重量的乘积。
每次合并小明只能合并位置相邻的两颗石子并将合并出的新石子放在原来的位置。
现在小明想用最少的胶水将所有石子粘在一起请帮助小明计算最少需要多少胶水。
输入格式 输入的第一行包含一个整数 n n n表示初始时的石子数量。
第二行包含 n 个整数 w 1 , w 2 , … , w n n个整数 w_1,w_2,…,w_n n个整数w1,w2,…,wn依次表示每颗石子的重量。
输出格式 一个整数表示答案。
数据范围 1 ≤ n ≤ 1 0 5 , 1≤n≤10^5, 1≤n≤105, 1 ≤ w i ≤ 1000 1≤w_i≤1000 1≤wi≤1000 输入样例1 3 3 4 5 输出样例1 47 输入样例2 8 1 5 2 6 3 7 4 8 输出样例2 546 代码(python版本)
nint(input())
arrlist(map(int,input().split()))
res0
cur0
for i in range(len(arr)):rescur*arr[i]curarr[i]
print(res)代码cpp版本
#include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL;int n;
const int N 1e510;
int arr[N];
int main()
{cinn;for (int i 0; i n; i )cinarr[i];LL res0,cur0; for (int i 0; i n; i ){rescur*arr[i];curarr[i];}coutresendl;return 0;
}思路
看到这题首先看一下数据范围为1e5思考一下那么最大的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn),最多时间不能超过这个。现在心里有数了就可以开始做题首先拿到题目首先暴力骗分 看一下常规思路。我们先模拟一下 假设现在有三个石头质量分别为 a 1 , a 2 a 3 a_1,a_2a_3 a1,a2a3那么 第一次将最左边的两个石头合并需要的胶水量就是 a 1 ∗ a 2 a_1*a_2 a1∗a2 现在只有两个石头了质量分别为 a 1 a 2 , a 3 a_1a_2,a_3 a1a2,a3 那么将这两个石头合并之后需要的胶水量是 ( a 1 a 2 ) ∗ a 3 (a_1a_2)*a_3 (a1a2)∗a3 一共需要的胶水量是 a 1 ∗ a 2 ( a 1 a 2 ) ∗ a 3 a_1*a_2(a_1a_2)*a_3 a1∗a2(a1a2)∗a3
假设现在有四个石头质量分别为 a 1 , a 2 , a 3 , a 4 a_1,a_2,a_3,a_4 a1,a2,a3,a4那么 第一次将最左边的两个石头合并需要的胶水量就是 a 1 ∗ a 2 a_1*a_2 a1∗a2 现在还有三个石头质量分别为 a 1 a 2 , a 3 , a 4 a_1a_2,a_3,a_4 a1a2,a3,a4 继续将左边的两个石头合并之后需要的胶水量是 ( a 1 a 2 ) ∗ a 3 (a_1a_2)*a_3 (a1a2)∗a3 现在只有两个石头质量分别为 a 1 a 2 a 3 , a 4 a_1a_2a_3,a_4 a1a2a3,a4 将剩余的两个石头合并需要的胶水量是 ( a 1 a 2 a 3 ) ∗ a 4 (a_1a_2a_3)*a_4 (a1a2a3)∗a4 一共需要的胶水量是 a 1 ∗ a 2 ( a 1 a 2 ) ∗ a 3 ( a 1 a 2 a 3 ) ∗ a 4 a_1*a_2(a_1a_2)*a_3(a_1a_2a_3)*a_4 a1∗a2(a1a2)∗a3(a1a2a3)∗a4
到这里就找到了规律就是胶水量为 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 a_1*a_2(a_1a_2)*a_3(a_1a_2a_3)*a_4(a_1a_2a_3a_4)*a_5......(a_1a_2...a_{n-1})*a_n a1∗a2(a1a2)∗a3(a1a2a3)∗a4(a1a2a3a4)∗a5......(a1a2...an−1)∗an
然后代码中cur代表当前的重量也就是上面的规律中的括号中的数。
