本文共 1937 字，大约阅读时间需要 6 分钟。
为了解决这个问题，我们需要找到一种方法来合并石子，使得在两种不同的合并方案下，得分总和分别最大化和最小化。由于石子是环形排列的，我们需要考虑循环的情况，通常这可以通过将问题转化为线性结构来处理。
动态规划 (DP) 算法：我们可以使用动态规划来解决这个问题。定义两个状态：
maxx[i][j] 表示从第 i 堆到第 j 堆合并后的最大得分。minn[i][j] 表示从第 i 堆到第 j 堆合并后的最小得分。状态转移方程：
maxx[i][j] 取决于 maxx[i][k] 和 maxx[k+1][j] 的最大值。minn[i][j] 取决于 minn[i][k] 和 minn[k+1][j] 的最小值。处理环形结构：由于石子是环形排列的，我们将其转换为线性结构来处理。具体来说，我们将数组扩展到 2n，然后处理所有可能的区间。
import sysdef main(): n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) a = [0] + a + a[:n] # 处理环，变成线结构，长度为 2n-1 sum_ = [0] * (2 * n + 1) for i in range(1, 2 * n + 1): sum_[i] = sum_[i-1] + a[i] INF = float('inf') max_dp = [[0] * (2 * n + 1) for _ in range(2 * n + 1)] min_dp = [[INF] * (2 * n + 1) for _ in range(2 * n + 1)] for i in range(1, 2 * n + 1): max_dp[i][i] = 0 min_dp[i][i] = 0 for l in range(2, n + 1): for i in range(1, 2 * n - l + 2): j = i + l - 1 for k in range(i, j): current_max = max_dp[i][k] + max_dp[k+1][j] + (sum_[j] - sum_[i-1]) if current_max > max_dp[i][j]: max_dp[i][j] = current_max current_min = min_dp[i][k] + min_dp[k+1][j] + (sum_[j] - sum_[i-1]) if current_min < min_dp[i][j]: min_dp[i][j] = current_min max_total = 0 min_total = INF for i in range(1, n+1): j = i + n - 1 if max_dp[i][j] > max_total: max_total = max_dp[i][j] if min_dp[i][j] < min_total: min_total = min_dp[i][j] print(min_total) print(max_total)if __name__ == "__main__": main() n 和每堆石子的数量。sum_，用于快速计算区间和。max_dp 和 min_dp 数组，用于存储最大和最小得分。max_dp 和 min_dp 数组。该方法通过动态规划有效地解决了环形结构下的石子合并问题，确保了计算的正确性和效率。
转载地址：http://ahku.baihongyu.com/