题解 | #石子合并#
石子合并
https://www.nowcoder.com/practice/3eef8d66b0fa4f71a8498974547fe670
解题思路
- 题目描述：
堆石子，每堆石子数量为
- 每次可以选择两堆合并，得分为两堆石子数量的乘积
- 求最大可能得分
- 解题策略：
- 观察发现，无论合并顺序如何，最终得分是所有可能的两两组合的乘积之和
- 因为每次合并后的新堆石子数量是加法，而得分是乘法
- 所以合并顺序不影响最终结果
代码
#include <iostream>
#include <vector>
using namespace std;
int getMaxScore(int n, vector<int>& stones) {
int maxScore = 0;
// 计算所有可能的两两组合的乘积之和
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
maxScore += stones[i] * stones[j];
}
}
return maxScore;
}
int main() {
int n;
cin >> n;
vector<int> stones(n);
for(int i = 0; i < n; i++) {
cin >> stones[i];
}
cout << getMaxScore(n, stones) << endl;
return 0;
}
import java.util.*;
public class Main {
static int getMaxScore(int n, int[] stones) {
int maxScore = 0;
// 计算所有可能的两两组合的乘积之和
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
maxScore += stones[i] * stones[j];
}
}
return maxScore;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] stones = new int[n];
for(int i = 0; i < n; i++) {
stones[i] = sc.nextInt();
}
System.out.println(getMaxScore(n, stones));
}
}
def get_max_score(n, stones):
max_score = 0
# 计算所有可能的两两组合的乘积之和
for i in range(n):
for j in range(i + 1, n):
max_score += stones[i] * stones[j]
return max_score
n = int(input())
stones = list(map(int, input().split()))
print(get_max_score(n, stones))
算法及复杂度
- 算法：数学方法
- 时间复杂度：
- 需要遍历所有可能的两两组合
- 空间复杂度：
- 需要存储
