石子合并算法：最小与最大得分计算

"该资源是一个Java程序，用于解决石子合并问题。问题描述为：有n堆石子在圆形操场的周围，每步可以合并相邻的两堆，合并后的新堆石子数量作为得分。目标是计算将所有石子合并成一堆时的最小得分和最大得分。程序通过输入文件读取石子的数量和各堆石子的初始数量，然后运用两个不同的类Merge1和Merge2分别计算最小得分和最大得分，并输出结果以及运行时间。" 在这个问题中，关键知识点包括： 1. **石子合并问题**：这是一个优化问题，涉及到动态规划或者贪心策略。每次合并选择相邻的两堆，目的是找到最优的合并顺序以达到最小或最大的得分。 2. **动态规划**：Merge1和Merge2类可能使用了动态规划方法来解决这个问题。动态规划是一种解决最优化问题的算法，通过构建子问题并存储其解，避免重复计算，从而提高效率。 3. **二维数组m[][]**：在代码中，m[][] 可能被用来存储子问题的解，其中m[i][j]表示前i堆和前j堆之间合并的最优得分。初始化时，m[g][g]=0表示单堆石子无需合并，得分自然为0。 4. **文件输入**：程序通过`Scanner`类从文件读取数据，例如石子的数量n和每堆石子的初始数量，这表明输入数据可能来自外部文件，如"MERGE9.IN"。 5. **类Merge1和Merge2**：这两个类是为了解决问题的核心算法，分别计算最小得分和最大得分。它们可能实现了不同的策略，例如Merge1可能使用矩阵链乘法的动态规划思想，而Merge2可能采用了不同的策略。 6. **性能度量**：程序还计算并输出了运行时间，这是对算法效率的一种评估，单位为毫秒。这部分代码使用了`System.nanoTime()`来获取程序运行的精确时间，然后计算与开始时间的差值。 7. **Java编程**：整个程序是用Java语言编写的，使用了面向对象的特性，如类和方法。`main`方法是程序的入口点，`Scanner`类用于文件读取，`File`类用于处理文件路径。 8. **异常处理**：`try-catch`结构用于处理可能出现的`FileNotFoundException`，确保程序在无法找到输入文件时能正常终止。 这个Java程序提供了一个解决石子合并问题的实例，涉及动态规划、文件输入、类的使用以及性能分析等多方面技术。