[蓝桥杯 2020 省 A1] 超级胶水

一.题目

题目描述

小明有 n 颗石子，按顺序摆成一排。

他准备用胶水将这些石子粘在一起。

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

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

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

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

输入格式

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

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

输出格式

输出一个整数代表答案。

数据范围

1 ≤ N ≤ 1000，
1 ≤ $w_i$ ≤ 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,\dots \dots ,a_k$}:
我们按要求先合并相邻：
一直合并头两项，则有f1 = ($a_1\ast a_2$) + ($a_1+a_2$) * $a_3$ + ($a_1+a_2+a_3$) * $a_4$ + …… + ($a_1+a_2+\dots \dots +a_{k-1}$) * $a_k$ = ($a_1\ast a_2$) + ($a_1\ast a_3$) + …… + ($a_1\ast a_k$) + ($a_2\ast a_3$) + …… + ($a_{k-1}\ast a_k$);
合并其他相邻两项结果也是一样的，可以自己列举。
和并不相邻的两项时，则有f2 = ($a_1\ast a_j$) + ($a_1+a_i$) * $a_j$ + ($a_1+a_i+a_j$) * $a_x$ + …… + ($a_1+a_i+a_j+\dots \dots +a_y$) * $a_z$ = ($a_1\ast a_2$) + ($a_1\ast a_3$) + …… + ($a_1\ast a_k$) + ($a_2\ast a_3$) + …… + ($a_{k-1}\ast a_k$);
的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;
}