一.题目
题目描述
小明有 n 颗石子，按顺序摆成一排。
他准备用胶水将这些石子粘在一起。
每颗石子有自己的重量，如果将两颗石子粘在一起，将合并成一颗新的石子，重量是这两颗石子的重量之和。
为了保证石子粘贴牢固，粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比，本题不考虑物理单位，认为所需要的胶水在数值上等于两颗石子重量的乘积。
每次合并，小明只能合并位置相邻的两颗石子，并将合并出的新石子放在原来的位置。
现在，小明想用最少的胶水将所有石子粘在一起，请帮助小明计算最少需要多少胶水。
输入格式
输入的第一行包含一个整数 n，表示初始时的石子数量。
第二行包含 n 个整数 w 1 , w 2 , … , w n w_1,w_2,…,w_n w1,w2,…,wn，依次表示每颗石子的重量。
输出格式
输出一个整数代表答案。
数据范围
1 ≤ N ≤ 1000，
1 ≤ w i w_i wi ≤ 1000
输入样例1
3
3 4 5
输出样例1
47
输入样例2
8
1 5 2 6 3 7 4 8
输出样例2
546
二.解释
看完题目，一眼贪心，想到之前做过的类似题目（合并石头、合并果子等），先找出相邻乘积最小的两项，按要求计算，但是这样只能过 80% 的数据。
直接计算最复杂的是在序列中找最小乘积的两项，
当n = 3，有序列 = {a，b， c}；
我们按要求先合并相邻：
合并a，b，则有f1 = （a * b）+ (a + b) * c = (a * b) + (b * c) + (a * c);
合并b，c，则有f2 = （b * c）+ (b + c) * a = (a * b) + (b * c) + (a * c);
合并不相邻：
合并a，c，则有f3 = （a * c）+ (a + c) * b = (a * b) + (b * c) + (a * c);
得f1 = f2 = f3；
当n = k，有序列 = { a 1 , a 2 , … … , a k a_1, a_2, ……, a_k a1,a2,……,ak}:
我们按要求先合并相邻：
一直合并头两项，则有f1 = ( a 1 ∗ a 2 a_1 * a_2 a1∗a2) + ( a 1 + a 2 a_1 + a_2 a1+a2) * a 3 a_3 a3 + ( a 1 + a 2 + a 3 a_1 + a_2 + a_3 a1+a2+a3) * a 4 a_4 a4 + …… + ( a 1 + a 2 + … … + a k − 1 a_1 + a_2 + …… + a_{k - 1} a1+a2+……+ak−1) * a k a_k ak = ( a 1 ∗ a 2 a_1 * a_2 a1∗a2) + ( a 1 ∗ a 3 a_1 * a_3 a1∗a3) + …… + ( a 1 ∗ a k a_1 * a_k a1∗ak) + ( a 2 ∗ a 3 a_2 * a_3 a2∗a3) + …… + ( a k − 1 ∗ a k a_{k - 1} * a_k ak−1∗ak);
合并其他相邻两项结果也是一样的，可以自己列举。
和并不相邻的两项时，则有f2 = ( a 1 ∗ a j a_1 * a_j a1∗aj) + ( a 1 + a i a_1 + a_i a1+ai) * a j a_j aj + ( a 1 + a i + a j a_1 + a_i + a_j a1+ai+aj) * a x a_x ax + …… + ( a 1 + a i + a j + … … + a y a_1 + a_i + a_j + …… + a_y a1+ai+aj+……+ay) * a z a_z az = ( a 1 ∗ a 2 a_1 * a_2 a1∗a2) + ( a 1 ∗ a 3 a_1 * a_3 a1∗a3) + …… + ( a 1 ∗ a k a_1 * a_k a1∗ak) + ( a 2 ∗ a 3 a_2 * a_3 a2∗a3) + …… + ( a k − 1 ∗ a k a_{k - 1} * a_k ak−1∗ak);
的f1 = f2;
因此合并顺序不会有影响结果，我们可以用一个小顶堆来取数据，每次pop顶端两个数，合并之后再加回堆中即可。
第二种方法，从上面的推导结果我们发现，最终结果都是序列中任意两个数相乘再相加，因此我们可以直接算，再 O(N) 的复杂度得出结果。
三.代码
暴力计算:
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>using namespace std;typedef long long int64;
const int MaxN = 1e5 + 10;int64 InN, InK, Res;
vector<int64> Ns;int main()
{cin >> InN;int a;for (int i = 1; i <= InN; i++){scanf("%d", &a);Ns.push_back(a);}while (Ns.size() > 1){int64 x = 0, y = 1, z = Ns[x] * Ns[y];//取出最小乘积的相邻两个数for (int i = 1; i < Ns.size() - 1; i++){if (z > Ns[i] * Ns[i + 1]){z = Ns[i] * Ns[i + 1];x = i, y = i + 1;}}//放到原位置Res += z;Ns[x] = Ns[x] + Ns[y];Ns.erase(Ns.begin() + y);}cout << Res;return 0;
}
堆优化：
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <set>using namespace std;typedef long long int64;
const int MaxN = 1e5 + 10;int64 InN, InK, Res;
int64 Ns[MaxN];
priority_queue<int64, vector<int64>, greater<int64>> PQ;int main()
{cin >> InN;int64 a;for (int i = 1; i <= InN; i++){scanf("%lld", &a);PQ.push(a);}//优化部分while (PQ.size() > 1){int64 A = PQ.top();PQ.pop();int64 B = PQ.top();PQ.pop();PQ.push(A + B);Res += A * B;}cout << Res;return 0;
}
第二种解法：
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>using namespace std;typedef long long int64;
const int MaxN = 1e5 + 10;int64 InN, InK, Res;
int64 Ns[MaxN];int main()
{cin >> InN;int64 a;for (int i = 1; i <= InN; i++){scanf("%lld", Ns + i);}int64 S = Ns[1];for (int i = 2; i <= InN; i++){Res += Ns[i] * S; //累加S += Ns[i]; //前i项的和}cout << Res;return 0;
}