[蓝桥杯 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;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

堆优化：

#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;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

第二种解法：

#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;
}
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
30
31
32
33
34
35
36
37
38